二叉搜索树的最小绝对差
题目
530. 二叉搜索树的最小绝对差 - 力扣(LeetCode)
解题思路
二叉搜索树的中序遍历结果就是一个递增的序列,只需要中序遍历,然后不断判断相邻节点的差是否是最小值。
代码
int min = 100005;
int pre = -1;
public int getMinimumDifference(TreeNode root) {
if(root==null)
return -1;
fun(root);
return min;
}
private void fun(TreeNode root) {
if(root==null)
return;
fun(root.left);
System.out.println(root.val);
if(pre==-1){
pre = root.val;
}else{
min = Math.min(min, root.val-pre);
pre=root.val;
}
fun(root.right);
}
二叉树中第k个最小的元素
题目
230. 二叉搜索树中第K小的元素 - 力扣(LeetCode)
解题思路
基于中序遍历的序列,直接获取第k个元素即可
代码
public int kthSmallest(TreeNode root, int k) {
if(root==null)
return -1;
List<Integer> list = new ArrayList<>();
fun2(root,list);
return list.get(k-1);
}
private void fun2(TreeNode root, List<Integer> list) {
if(root==null)
return;
fun2(root.left,list);
System.out.println(root.val);
list.add(root.val);
fun2(root.right,list);
}
验证二叉搜索树
题目
解题思路
根据二叉搜索的特性
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
代码
public boolean isValidBST(TreeNode root) {
return fun3(root,Long.MAX_VALUE,Long.MIN_VALUE);
}
private boolean fun3(TreeNode root, long maxValue, long minValue) {
if(root==null)
return true;
if(root.val<=minValue||root.val>=maxValue){
return false;
}
return fun3(root.left,root.val,minValue)&&fun3(root.right,maxValue,root.val);
}