leetcode二叉搜索树部分笔记

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

1. 二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

解题思路： 二叉搜索树，大小是 左 根 右。
首先确定边界条件： 当root == null时，直接返回。
其次每次递归逻辑：需要从小到大开始，首先去找二叉搜索树的最小值，也就是最左边的节点，找到后，判断pre是否为-1，如果是-1，则仅记录当前节点的值即可。如果不是-1，则说明当前节点比pre大，需要计算两者差值，然后pre更新为当前节点。
最后再去递归右子树节点。

class Solution {
    int pre;
    int ans;

   public int getMinimumDifference(TreeNode root) {
        ans = Integer.MAX_VALUE;
        pre = -1;
        dfs(root);
        return ans;
    }

    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (pre == -1) {
            pre = root.val;
        } else {
            ans = Math.min(ans, root.val - pre);
            pre = root.val;
        }
        dfs(root.right);
    }
}

2. 二叉搜索树中第 K 小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

解题思路： 中序遍历，然后存入list集合中，然后用list.get（k-1)即可。

class Solution {
    List<Integer> list = new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        dfs(root);
        return list.get(k-1);
    }
    public void dfs(TreeNode root){
        if(root == null){
            return;
        }
        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
    }
}

3. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左
子树
只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

解题思路： 中序遍历，判断左子树、根节点、右子树的值是否能遵循二叉搜索树，如果不遵循则让statue等于1，然后返回fasle。

class Solution {
    Long pre;
    int state;
    public boolean isValidBST(TreeNode root) {
        pre = Long.MIN_VALUE;
        state = 0;
        dfs(root);
        if(state == 1){
            return false;
        }
        return true;

        
    }
    public void dfs(TreeNode root){
        if(root == null){
            return;
        }
        dfs(root.left);
        
        if(pre == Long.MIN_VALUE){
            pre = (long)root.val;
        }else{
            if(pre >= root.val){
                state = 1;
            }
            pre = (long)root.val;
        }
        dfs(root.right);
    }
}