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

https://leetcode.cn/problems/minimum-absolute-difference-in-bst/
中序遍历找最小值。

class Solution {
    int min=Integer.MAX_VALUE;
    TreeNode prev;
    public int getMinimumDifference(TreeNode root) {
        if(root.left!=null&&getMinimumDifference(root.left)<min){
            min=getMinimumDifference(root.left);
        }
        if(prev!=null&&root.val-prev.val<min){
            min=root.val-prev.val;
        }
        prev=root;
        if(root.right!=null&&getMinimumDifference(root.right)<min){
            min=getMinimumDifference(root.right);
        }
        return min;
    }
}

501. 二叉搜索树中的众数

https://leetcode.cn/problems/find-mode-in-binary-search-tree/
中序遍历map记录指和出现次数，同时记录最大值和size，用例都通过了，但是超出时间限制，不知为何。

class Solution {
    HashMap<Integer,Integer> map=new HashMap<>();
    int max=0;
    int size;
    public int[] findMode(TreeNode root) {
        find(root);
        int[] res=new int[size];
        int i=0;
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            if(entry.getValue()==max){
                res[i]=entry.getKey();
                i++;
            }
        }
        return res;
    }
    private void find(TreeNode root) {
        if(root==null) return;
        findMode(root.left);
        map.put(root.val,map.getOrDefault(root.val, 0) + 1);
        if(map.get(root.val)>max){
            max=map.get(root.val);
            size=0;
        }
        if(map.get(root.val)==max) size++;
        findMode(root.right);
    }
}

改成这样通过了，清楚无用map，但用时为2653ms，依然是一个庞大的数字。

class Solution {
    HashMap<Integer,Integer> map=new HashMap<>();
    int max=-1;
    int size;
    public int[] findMode(TreeNode root) {
        find(root);
        int[] res=new int[size];
        int i=0;
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            if(entry.getValue()==max){
                res[i]=entry.getKey();
                i++;
            }
        }
        return res;
    }
    private void find(TreeNode root) {
        if(root==null) return;
        findMode(root.left);
        map.put(root.val,map.getOrDefault(root.val, 0) + 1);
        if(map.get(root.val)>max){
            max=map.get(root.val);
            map.clear();
            map.put(root.val,max);
            size=0;
        }
        if(map.get(root.val)==max) size++;
        findMode(root.right);
    }
}

不用map时间是21ms

class Solution {
    ArrayList<Integer> resList=new ArrayList<Integer>();
    int max=0;
    int size=0;
    TreeNode pre=null;
    public int[] findMode(TreeNode root) {
        find(root);
        int[] res=new int[resList.size()];
        int i=0;
        for(int k : resList){
            res[i]=k;
            i++;
        }
        return res;
    }
    private void find(TreeNode root) {
        if(root==null) return;
        findMode(root.left);
        if (pre == null || root.val != pre.val) {
            size = 1;
        } else {
            size++;
        }
        if(size>max){
            max=size;
            resList.clear();
            resList.add(root.val);
        }else if(size==max){
            resList.add(root.val);
        }
        pre=root;
        findMode(root.right);
    }
}

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

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
如果找到是某根节点，另一个在根节点的子树中则返回该根节点，另一种情况是分属于两个子树，则根节点为遍历到此的根节点。但是没有头绪了、。应该用后序遍历。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == q || root == p || root == null) return root;
        if(p.left==q||p.right==q) return p;
        if(q.left==p||q.right==p) return q;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null && right == null) {
            return null;
        }else if(left == null && right != null) {
            return right;
        }else if(left != null && right == null) {
            return left;
        }else { // 若找到两个节点
            return root;
        }
    }
}