代码随想录训练营第二十一天 ｜ 530.二叉搜索树的最小绝对差，501.二叉搜索树中的众数，236. 二叉树的最近公共祖先

 今天是第二十一天，还是二叉树，做了得有一周的二叉树了

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

class Solution {
    int res = Integer.MAX_VALUE;
    TreeNode pre = null;
    public int getMinimumDifference(TreeNode root) {
        getMin(root);
        return res;
    }
    public void getMin(TreeNode root){
        if(root == null){
            return;
        }
        getMin(root.right);
        if(pre!=null){
            res = Math.min(Math.abs(root.val - pre.val),res);
        }
        pre = root;
        getMin(root.left);
    }
}

因为中间节点的值在左右节点之间，因此最小的值一定是左右的一个节点与中间结点的差。

501.二叉搜索树中的众数 

class Solution {
    int preVal = 0, curTimes = 0, maxTimes = 0;
    ArrayList<Integer> list = new ArrayList<Integer>();
    public int[] findMode(TreeNode root) {
    traversal(root);
    //list转换为int[]
    int size = list.size();
    int[] ans = new int[size];
    for(int i = 0; i < size; i++){
        ans[i] = list.get(i);
    }
    return ans;
    }
    //二叉搜索树中序遍历是递增顺序
    public void traversal(TreeNode root){
    if(root != null){
        traversal(root.left);
        //判断当前值与上一个值的关系, 更新 curTimes 和 preVal
        if(preVal == root.val){
        curTimes++;
        }else{
        preVal = root.val;
        curTimes = 1;
        }
        //判断当前数量与最大数量的关系, 更新 list 和 maxTimes
        if(curTimes == maxTimes){
        list.add(root.val);
        }else if(curTimes > maxTimes){
        list.clear();
        list.add(root.val);
        maxTimes = curTimes;
        }
        traversal(root.right);
    }
    }
}

中序遍历二叉搜索树就相当于遍历递增顺序的有序数组

236. 二叉树的最近公共祖先 

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return root;
        }
        if(root == p || root == q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p , q);
        if (left != null && right != null){
            return root;
        }
        if(left != null){
            return left;
        }
        
        if(right != null){
            return right;
        }
        return null;
    }
}

如果root 是p或者q，就说明公共祖先是p或者q的本身，直接返回就可以，不然就进行递归，如果在递归结束后两遍仍然没有探到底，就说明本身root就是公共祖先，返回即可。不然就看那边是非null，公共祖先就出现在哪里。再一层一层传递回去

今天还是二叉树