Leetcode(236) Lowest Common Ancestor of a Binary Tree

发表于 | 分类于

Description

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

img

Example 1:

1
2
3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

1
2
3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Note:

  • All of the nodes’ values will be unique.
  • p and q are different and both values will exist in the binary tree.

解法

我的思路是构造一个哈希表存储每个节点的直接父节点，然后将到根节点的路径记录下来，利用hashset找到第一个冲突的点。

具体代码如下：

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    HashMap<TreeNode,TreeNode> helper = new HashMap<>();
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        helper.put(root,root);
        iterate(root);
        HashSet<TreeNode> hs = new HashSet<>();
        hs.add(p);
        while(helper.get(p)!=p){
            hs.add(helper.get(p));
            p = helper.get(p);
        }
        if(hs.contains(q)){
            return q;
        }
        hs.add(q);
        while(helper.get(q)!=q){
            if(hs.contains(helper.get(q))){
                return helper.get(q);
            }
            hs.add(helper.get(q));
            q = helper.get(q);
        }
        return null;
    }
    void iterate(TreeNode root){
        if(root == null){
            return;
        }
        if(root.left!=null){
            helper.put(root.left,root);
        }
        if(root.right!=null){
            helper.put(root.right,root);
        }
        iterate(root.left);
        iterate(root.right);
    }
}

这题同样可以用递归来解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || p == root || q == root){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left != null && right != null){
            return root;
        }
        return left == null ? right : left;
    }
}