java算法day19

java算法day19

• 501 二叉搜索树中的众数
• 530 二叉搜索树的最小绝对值差
• 236 二叉树的最近公共祖先
• 235 二叉搜索树的最近公共祖先

---

501 二叉搜索树中的众数

我第一时间想到的方法是遍历二叉树+哈希。哈希用来统计数字出现的次数。之后遍历map收集结果。
坏处就是效率比较低

class Solution {
    Map<Integer,Integer> map = new HashMap<>();

    public int[] findMode(TreeNode root) {
        dfs(root);
        int mostValue = Integer.MIN_VALUE;
        List<Integer> result = new ArrayList<>();
        for(Map.Entry<Integer,Integer> entry : map.entrySet() ){
            int currentCount = entry.getValue();
            if(currentCount>mostValue){
                mostValue = currentCount;
            }
        }
        //找出最大的出现次数了。接下来做匹配去找符合这个次数的元素
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(entry.getValue()==mostValue){
                result.add(entry.getKey());
            }
        }
		//如果不喜欢这个方法，也可以用传统方法，遍历List收集结果
        return result.stream().mapToInt(Integer::intValue).toArray();

        
    }

    void dfs(TreeNode root){
        if(root==null){
            return;
        }
        //这个方法比较常用，我当时想用没记起来
        //这个是如果获取出来为空，那就给他赋一个默认值。
        int count = map.getOrDefault(root.val,0);
        map.put(root.val,count+1);

        dfs(root.left);
        dfs(root.right);

    }
    
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

---

高效的做法
利用了BST的性质，即BST的中序序列是有序序列
这个也是本题学到的一个很好的知识点。

class Solution {
    ArrayList<Integer> res = new ArrayList<>();
    int count=0;
    int maxCount = Integer.MIN_VALUE;
    TreeNode pre = null;
    
    void dfs(TreeNode root){
        //递归出口
        if(root==null){
            return;
        }
        //中序遍历,所以先递归左子树
        dfs(root.left);
        //这里才是处理根节点
        if(pre!=null && root.val==pre.val){
            //这里表明与前一个节点值相等，所以累计众数
            count++;
        }else{
            //能到这里说明，pre=null即树的根节点，或者root.val!=pre.val即是新的不同节点
            count = 1;
        }
        if(count==maxCount){
            //如果计数达到了最大值，就加入结果集
            res.add(root.val);
        }
        if(count>maxCount){
            //说明超过了最大值，由于众数可能有多个，所以之前收集的最大值就不是最大值了
            //所以之前收集的结果集要清空
            res.clear();
            //更新最新的最大值
            maxCount = count;
            //把当前的这个新众数加入结果集
            res.add(root.val);
        }
        //更新前一个节点为当前root，因为root要递归到下一个地方去了。当前节点已经处理完
        //所以对即将遍历下一个节点而言，pre是当前root。
        pre = root;
        dfs(root.right);
    }


    public int[] findMode(TreeNode root) {
        dfs(root);
        //收集结果
        int size = res.size();
        int[] ans = new int[size];
        for(int i = 0;i<size;i++){
            ans[i]=res.get(i);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

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

就是利用BST的中序序列有序的性质。结果最小绝对值差肯定在序列相邻元素之间。所以这题的思路和上题差不多，就是中序遍历，并且遍历的时候计算currentNode和preNode的差值。

class Solution {
    TreeNode pre = null;
    int min = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
        dfs(root);
        return min;
    }

    void dfs(TreeNode root){
        if(root==null){
            return;
        }
        dfs(root.left);
        
        if(pre!=null){
            //不等于null那么就二者之间计算一下差值
            int sub = root.val-pre.val;
            //然后做一下正负判断
            int currenSub = 0;
            if(sub<0){
                currenSub = -sub;
            }else{
                currenSub = sub;
            }
            //然后准备判断更新min
            if(currenSub<min){
                min = currenSub;
            }
            
        }


        pre = root;
        dfs(root.right);
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

---

236 二叉树的最近公共祖先

今天遇到的最难的题目。代码很简短，但是理解很痛苦。

首先需要明确的一点，手算我们都清楚，公共节点怎么找，那就是先看图，然后找到两个目标节点，然后往上找他们第一个交汇的节点，那么这个节点就是他的最近公共祖先节点。

所以从这个过程来看，找公共节点，还是应该用后序遍历，即先深入某点的左右子树，最后到根节点来判断。

知道了用哪种递归方式，那么就要清楚在递归的过程中，如何进行判断哪个节点是最近公共祖先。
判断公共祖先，需要通过分类来完成。

也许看完这个你还是很懵，感觉像在背套路，那么就跟着代码来模拟一下。
在模拟之前需要明确，用的是后序。所以最近公共祖先结果的处理是从底部开始的。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    //这个是递归出口，这里不但是递归出口，还做了剪枝。
    //我觉得在想递归出口的时候，要联系上一层来看，不然会很懵。这就相当于提前为上一层返回结果了。
        if(root == null || root == p || root == q) return root;
        //后序遍历递归左右子树
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //这里处理结果非常的精妙
        //这三行代码甚至包括了三种情况，如果始终返回left或者right，那么这代表了p是q的最近祖先或者q是p的最近祖先。
        //但是如果返回的过程中，碰到了left，right都不为null，也就是返回root。那么结果就变成了，某个节点是p和q的最近公共祖先的情况，然后把该点的结果一直向上传递。
        if(left == null) return right;
        if(right == null) return left;
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

235 二叉搜索树的最近公共祖先

这个题相比上一题难度小很多，依据二叉搜索树的性质，直接解决。
如果p，q的值都比root小，那么p，q在root的左子树，那么往左子树去递归寻找。反之如果p，q的值都比root大，那么p，q在root的右子树，那么去递归右子树去找。
那么剩下就包含了符合结果的三种情况。
1.p或q为最近公共祖先
2.p<root<q或p>root>q。
此时root都是最近公共祖先。所以返回root。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p.val<root.val && q.val<root.val){
            return lowestCommonAncestor(root.left,p,q);
        }else if(p.val>root.val && q.val>root.val){
            return lowestCommonAncestor(root.right,p,q);
        }else{
            return root;
        }
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

---