Day31——二叉树专题

---

25.二叉搜索树中的众数

题目链接：501. 二叉搜索树中的众数 - 力扣（LeetCode）

思路：利用二叉搜索树的特性，采用中序遍历。二叉搜索数的性质进行求解（双指针比较当前节点和前驱节点，计数, 更新等）

代码实现思路：

class Solution {
    List<Integer> list = new ArrayList<>();
    int pre = -1;
    int count = 0;
    int Maxcount = 0;
    public int[] findMode(TreeNode root) {
        dfs(root);
        int[] res = new int[list.size()];
        for(int i = 0;i<list.size();i++){
            res[i] = list.get(i);
        }
        return res;
    }
    public void dfs(TreeNode root){
        if(root==null){
            return ;
        }
        //向左遍历
        dfs(root.left);
        if(root.val==pre){
            count++;
        }else{
            count = 1;
        }
        pre = root.val;
        if(count==Maxcount){
            list.add(root.val);
        }else if(count>Maxcount){
            Maxcount = count;
            list.clear();
            list.add(root.val);
        }
        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

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

题目链接：236. 二叉树的最近公共祖先 - 力扣（LeetCode）

思路：dfs后序遍历，从低往上搜索公共祖先

1. 求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从低向上的遍历方式。
2. 在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。

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

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

题目链接：235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

思路：利用二叉搜索树的性质：左子树的值都比跟小，右子树的值都比根大，这样我们就可以确定搜索的方向了！

• 如果当前根节点root的值 比 q p大，那么说明p q的最近公共节点在左子树，我们遍历左子树即可
• 如果当前根节点root的值 比 q p小，那么说明p q的最近公共节点在右子树，我们遍历左子树即可
• p q各位于当前root的左右子树，那么此时root即为最近公共祖先

Code:

递归法：

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

迭代法：

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