day21

501. 二叉搜索树中的众数

class Solution {
    List<Integer> result=new ArrayList<Integer>();
    int base,count,maxCount;              //用base来存当前的众数值，count存放当前众数的个数，maxCount存放已经放入数组中的个数最多众数的长度
    public int[] findMode(TreeNode root) {
        dfs(root);
        int[] arr=new int[result.size()];
        for(int i=0;i<result.size();i++){
            arr[i]=result.get(i);
        }
        return arr;

    }
    public void dfs(TreeNode root){
        if(root==null) return;  //1 

        dfs(root.left);    //   中序遍历    左
        
		
		//中 的处理逻辑
		if(base==root.val){  //当前root和base比较  如果是同一个值  则 count++
            count++;
        }else{            //否则就换下一个值进行统计（因为是搜索树，使用中序遍历，已经是有序，所以下一个不是一样的，那之后肯定没有一样的数了）
            count=1;
            base=root.val;
        }
        if(maxCount==count){      //count和 maxCount 比较，如果比他大，就把之前的删除，把他放进去，如果一样大，就一起放如数组
            result.add(base);
        }
        if(count>maxCount){
            result.clear();
            maxCount=count;
            result.add(base);
        }
        dfs(root.right);   //右
    }
}

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

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;            //当越过叶节点，则直接返回 nullnull ；
                                                
        if(root==q||root==p) return root;       //当 rootroot 等于 p, qp,q ，则直接返回 rootroot 

        TreeNode left=lowestCommonAncestor(root.left,p,q);     //开启递归左子节点，返回值记为 leftleft 
        TreeNode right=lowestCommonAncestor(root.right,p,q);  //开启递归右子节点，返回值记为 rightright


//当 leftleft 和 rightright 同时为空 ：说明 rootroot 的左 / 右子树中都不包含 p,qp,q ，返回 nullnull ；
        if(left==null&&right==null) return null;  
 //当 leftleft 和 rightright 同时不为空 ：说明 p, qp,q 分列在 rootroot 的 异侧 （分别在 左 / 右子树），因此 rootroot 为最近公共祖先，返回 rootroot 
        if(left!=null&&right!=null) return root;

//当 leftleft 为空 ，rightright 不为空 ：p,qp,q 都不在 rootroot 的左子树中，直接返回 rightright 。具体可分为两种情况：   
        if(left==null) return right;
        if(right==null) return left;
        return root;

    }
}