Day16 二叉树part06| LeetCode 530.二叉搜索树的最小绝对差 ，501.二叉搜索树中的众数，236. 二叉树的最近公共祖先

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

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

class Solution {
        public  List<Integer>  res = new ArrayList<>();
       
        void traversal(TreeNode root)
        {
            if(root==null) return ;

            traversal(root.left);
            res.add(root.val);
            traversal(root.right);
        }
        public int getMinimumDifference(TreeNode root) {

            traversal(root);
            if(res.size()<2)
            {
                return 0;
            }
              int minVal=Integer.MAX_VALUE;
            for(int i=1;i<res.size();i++)
            {
             minVal=Math.min(minVal, res.get(i)-res.get(i-1));
            }

            return minVal;
        }
    }

501.二叉搜索树中的众数

501. 二叉搜索树中的众数

  class Solution {
        List<Integer> list=new ArrayList<>();
        int count=0;
        int MaxCount=0;
        TreeNode pre=null;

        public void find(TreeNode root)
        {
            if(root==null) return;
            //中序遍历
             find(root.left);
            //计数
            if(pre==null||root.val!=pre.val)
            {
                count=1;
            }
            else
            {
                count++;
            }
            //更新maxCount
            if(count>MaxCount)
            {
                MaxCount=count;
                list.clear();
                list.add(root.val);
            }
            else if(count==MaxCount)
            {
                //多个众数的情况
                list.add(root.val);
            }
            pre=root;
            find(root.right);
        }
        public int[] findMode(TreeNode root) {
            count=0;
            MaxCount=0;
            pre=null;
            find(root);

            int[] res=new int[list.size()];
            for(int i=0;i<res.length;i++)
            {
                res[i]=list.get(i);
            }
            return res;
        }
    }

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

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

 class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

            if(root==null) return null;
            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&&right!=null) return right;
            else if(left!=null&& right==null) return left;
            else
            {
                return null;
            }

        }
    }