day20

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

class Solution {
    private int res = Integer.MAX_VALUE;
    private TreeNode pre;

    public void traversal(TreeNode node) {
        if(node == null) {
            return;
        }

        traversal(node.left);
        if(pre != null){
            res = Math.min(res, node.val-pre.val);
        }
        pre = node;
        traversal(node.right);

    }

    public int getMinimumDifference(TreeNode root) {
        traversal(root);
        return res;
    }
}

2、501.二叉搜索树中的众数

class Solution {
    ArrayList<Integer> resList;
    int count;
    int maxCount;
    TreeNode pre;

    public void traversal(TreeNode node) {
        if(node == null) {
            return;
        }

        traversal(node.left); //左

                              //中  
        if(pre == null){
            count = 1;
        } else if(pre.val == node.val){
            count++;
        }else{
            count = 1;
        }
        pre = node;

        if(count == maxCount){
            resList.add(node.val);
        }
        if(count > maxCount){
            maxCount = count;
            resList.clear();
            resList.add(node.val);
        }

        traversal(node.right); //右

        return;
    }

    public int[] findMode(TreeNode root) {
        resList = new ArrayList<>();
        maxCount = 0;
        count = 0;
        pre = null;
        
        traversal(root);
        int[] res = new int[resList.size()];
        for(int i=0; i<resList.size(); i++){
            res[i] = resList.get(i);
        }
        return res;
    }
}

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

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==q || root==p || root==null){
            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 && right!=null){
            return right;
        } else if(left!=null && right==null){
            return left;
        } else {
            return null;
        }

    }
}