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

原始思路

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
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        ArrayList<TreeNode> listP = new ArrayList<>();
        ArrayList<TreeNode> listQ = new ArrayList<>();
        findNode(root, p, listP);
        findNode(root, q, listQ);

        //数组倒序遍历,最近的公共数字就是最近公共祖先
        for(int i = listP.size() -1; i >=0; i--){
            if(listQ.contains(listP.get(i))){
                return listP.get(i);
            }
        }
        return null;
    }

    //回溯算法
    public boolean findNode(TreeNode root, TreeNode target, ArrayList<TreeNode> list){

        //遍历到最后还没找到返回false
        if(root == null){
            return false;
        }

        //如果没有找到目标节点,添加节点到路径中
        if (!list.contains(target)){
            list.add(root);
        }

        //如果找到了目标节点,则返回
        if(list.contains(target)){
            return true;
        }

        //DFS查找
        if(!findNode(root.left, target, list)){
            list.remove(root.left);
        }else {
            return true;
        }

        if(!findNode(root.right, target, list)){
            list.remove(root.right);
        }else {
            return true;
        }

        return false;
    }
}

题解思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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);
         // 最近公共祖先在右边
         if(left == null){
             return right;
         }
         // 最近公共祖先在左边边
         if(right == null){
             return left;
         }
         //p q分散在两边
         return root;
     }
}