IVN
0%

LCA

Posted on Edited on In
Symbols count in article: 11k Reading time ≈ 10 mins.

Lowest Common Ancestor选编

基本框架: find(root,val)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 定义：在以 root 为根的二叉树中寻找值为 val 的节点
TreeNode find(TreeNode root, int val) {
    // base case
    if (root == null) {
        return null;
    }
    // 看看 root.val 是不是要找的
    if (root.val == val) {
        return root;
    }
    // root 不是目标节点，那就去左子树找
    TreeNode left = find(root.left, val);
    if (left != null) {
        return left;
    }
    // 左子树找不着，那就去右子树找
    TreeNode right = find(root.right, val);
    if (right != null) {
        return right;
    }
    // 实在找不到了
    return null;
}

如果一个节点能够在它的左右子树中分别找到p和q，则该节点为LCA节点。

一旦发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 定义：在以 root 为根的二叉树中寻找值为 val1 或 val2 的节点
TreeNode find(TreeNode root, int val1, int val2) {
    // base case
    if (root == null) {
        return null;
    }
    // 前序位置，看看 root 是不是目标值
    if (root.val == val1 || root.val == val2) {
        return root;
    }
    // 去左右子树寻找
    TreeNode left = find(root.left, val1, val2);
    TreeNode right = find(root.right, val1, val2);
    // 后序位置，已经知道左右子树是否存在目标值

    return left != null ? left : right;
}

236. Lowest Common Ancestor of a Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LeetCode236 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return find(root,p.val,q.val);
    }

    TreeNode find(TreeNode root, int p, int q){
        if(root==null){
            return null;
        }
        if(root.val==p || root.val==q){
            return root;
        }
        TreeNode left=find(root.left,p,q);
        TreeNode right=find(root.right,p,q);
        if(left!=null && right!=null){ //如果左右子树都找到一个，则LCA为当前root
            return root;
        }else{//否则LCA在左子树中或右子树中
            return left!=null ? left : right;
        }
    }
}

235. Lowest Common Ancestor of a Binary Search Tree

法一：递归写法

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

法二：迭代写法

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

1650. Lowest Common Ancestor of a Binary Tree III

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
public class LeetCode1650 {
    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node parent;
    };


    public Node lowestCommonAncestor(Node p, Node q) {
        Set<Node> set=new HashSet<>();
        while(p!=null || q!=null){
            if(p!=null){
                if(set.contains(p)){
                    return p;
                }
                set.add(p);
                p=p.parent;
            }
            if(q!=null){
                if(set.contains(q)){
                    return q;
                }
                set.add(q);
                q=q.parent;
            }
        }
        return null;
    }
}

742. Closest Leaf in a Binary Tree

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class Solution {
    public int findClosestLeaf(TreeNode root, int k) {
        Map<TreeNode, Integer> map = new HashMap<>();
        getDistance(root, map, 0);
        TreeNode node = findNode(root, k);
        int res = Integer.MAX_VALUE, minDist = Integer.MAX_VALUE;
        
        for (TreeNode cur : map.keySet()) {
            if (cur.left == null && cur.right == null) {
                TreeNode lca = lowestCommonAncestor(root, node, cur);
                int curDist = map.get(node) + map.get(cur) - 2 * map.get(lca);
                
                if (curDist < minDist) {
                    minDist = curDist;
                    res = cur.val;
                }
            }
        }
        
        return res;
    }
    
    // get distance from root to each node
    private void getDistance(TreeNode root, Map<TreeNode, Integer> map, int dist) {
        if (root == null) {
            return;
        }
        map.put(root, dist);
        getDistance(root.left, map, dist + 1);
        getDistance(root.right, map, dist + 1);
    }
    
    private 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;
        }
        return left == null ? right : left;
    }
    
    // get the node whose value equals k recursively.
    private TreeNode findNode(TreeNode root, int k) {
        if (root.val == k) {
            return root;
        }
        if (root.left != null) {
            TreeNode left = findNode(root.left, k);
            if (left != null) {
                return left;
            }
        }
        if (root.right != null) {
            TreeNode right = findNode(root.right, k);
            if (right != null) {
                return right;
            }
        }
        return null;
    }
    
    // get the node whose value equals k iteratively.
    // private TreeNode findNode2(TreeNode root, int k) {
    //     if (root == null) {
    //         return null;
    //     }
    //     Deque<TreeNode> stack = new ArrayDeque<>();
    //     TreeNode p = root;
    //     while (!stack.isEmpty() || p != null) {
    //         if (p != null) {
    //             if (p.val == k) {
    //                 return p;
    //             }
    //             stack.push(p);
    //             p = p.left;
    //         } else {
    //             p = stack.pop();
    //             p = p.right;
    //         }
    //     }
    //     return root;
    // }
}

神之一手：

  • int curDist = map.get(node) + map.get(cur) - 2 * map.get(lca);
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
53
54
55
56
Map<TreeNode,Integer> map=new HashMap<>();
public int findClosestLeaf(TreeNode root, int k) {
    getDist(root,0);
    TreeNode target=find(root,k);
    int res=Integer.MAX_VALUE;
    int min=Integer.MAX_VALUE;
    for (TreeNode node : map.keySet()) {
        if(node.left==null && node.right==null){
            TreeNode p=lca(root,k,node.val);
            int cur=map.get(target)+map.get(node)-2*map.get(p);
            if(cur<min){
                res=node.val;
                min=cur;
            }
        }
    }
    return res;
}

void getDist(TreeNode node, int i){
    if(node==null){
        return;
    }
    map.put(node,i);
    getDist(node.left,i+1);
    getDist(node.right,i+1);
}

TreeNode find(TreeNode node, int k){
    if(node==null){
        return null;
    }
    if(node.val==k){
        return node;
    }
    TreeNode left=find(node.left,k);
    if(left!=null){
        return left;
    }
    return find(node.right,k);
}

TreeNode lca(TreeNode node, int p, int q){
    if(node==null){
        return null;
    }
    if(node.val==p || node.val==q){
        return node;
    }
    TreeNode left=lca(node.left,p,q);
    TreeNode right=lca(node.right,p,q);
    if(left!=null && right!=null){
        return node;
    }
    return left!=null ? left : right;
}

863. All Nodes Distance K in Binary Tree

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
Map<TreeNode,Integer> map=new HashMap<>();
  //int curDist =
  // map.get(node) + map.get(cur) - 2 * map.get(lca);
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
    List<Integer> res=new ArrayList<>();
    Deque<TreeNode> q=new LinkedList<>();
    q.offer(root);
    getDist(root,0);
    for (TreeNode node : map.keySet()) {
        TreeNode p=lca(root,node.val,target.val);
        int dist=map.get(node)+map.get(target)-2*map.get(p);
        if(dist==k){
            res.add(node.val);
        }
    }
    return res;
}

void getDist(TreeNode node, int d){
    if(node==null){
        return;
    }
    map.put(node,d);
    getDist(node.left,d+1);
    getDist(node.right,d+1);
}

TreeNode lca(TreeNode node, int p, int q){
    if(node==null){
        return null;
    }
    if(node.val==p || node.val==q){
        return node;
    }
    TreeNode left=lca(node.left,p,q);
    TreeNode right=lca(node.right,p,q);
    if(left!=null && right!=null){
        return node;
    }
    return left==null ? right : left;
}

865. Smallest Subtree with all the Deepest Nodes

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
Map<TreeNode, Integer> map=new HashMap<>();
public TreeNode subtreeWithAllDeepest(TreeNode root) {
    dist(root,0);
    Deque<TreeNode> q=new LinkedList<>();
    int max=0;
    for (TreeNode node : map.keySet()) {
        if(node.left==null && node.right==null){
            int d=map.get(node);
            if(d>max){
                q.clear();
                q.offer(node);
                max=d;
            }else if(d==max){
                q.offer(node);
            }
        }
    }
    while(q.size()>1){
        TreeNode a=q.poll();
        TreeNode b=q.poll();
        q.offer(lca(root,a.val,b.val));
    }
    return q.poll();
}

void dist(TreeNode node, int d){
    if(node==null){
        return;
    }
    map.put(node,d);
    dist(node.left,d+1);
    dist(node.right,d+1);
}

TreeNode lca(TreeNode node, int p, int q){
    if(node==null){
        return null;
    }
    if(node.val==p || node.val==q){
        return node;
    }
    TreeNode left=lca(node.left,p,q);
    TreeNode right=lca(node.right,p,q);
    if(left!=null && right!=null){
        return node;
    }
    return left==null ? right : left;
}

1676. Lowest Common Ancestor of a Binary Tree IV

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
    Set<Integer> set=new HashSet<>();
    for (TreeNode node : nodes) {
        set.add(node.val);
    }
    return lca(set,root);
}

private TreeNode lca(Set<Integer> set, TreeNode root){
      if(root==null){
          return null;
      }
      if(set.contains(root.val)){
          return root;
      }
      TreeNode l=lca(set,root.left);
      TreeNode r=lca(set,root.right);
      if(l!=null && r!=null){
          return root;
      }
      return l==null ? r : l;
}

1644. Lowest Common Ancestor of a Binary Tree II

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
boolean found=false;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode res=lca(root,p,q);
    return found ? res : null;
}

TreeNode lca(TreeNode root, TreeNode p, TreeNode q){
    if(root==null){
        return null;
    }
    TreeNode l=lca(root.left,p,q);
    TreeNode r=lca(root.right,p,q);
    int condition=0;
    if(root.val==p.val || root.val==q.val){
        condition++;
    }
    if(l!=null){
        condition++;
    }
    if(r!=null){
        condition++;
    }
    if(condition==2){
        found=true;
    }
    if(root.val==p.val || root.val==q.val || (l!=null && r!=null)){
        return root;
    }
    return l!=null ? l : r;
}

Follow up: Can you find the LCA traversing the tree, without checking nodes existence?

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii/discuss/923721/Python-Eulerian-Tour-with-pictures

Euler Path of the binary tree: root, left, root, right, 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#python 太慢了！
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

    def euler_tour(node, d):
	    nonlocal path, depth, p, q, p_found, q_found
        
	    if p_found and q_found: return None
	    if node == p: p_found = True
	    if node == q: q_found = True

	    path.append(node)
	    depth.append(d)

	    if node.left:
		    euler_tour(node.left, d+1)
		    path.append(node)
		    depth.append(d)

	    if node.right:
		    euler_tour(node.right, d+1)
		    path.append(node)
		    depth.append(d)

    # 1. Build an Eulerian Path of the tree
    path, depth = [], []
    p_found, q_found = False, False
    euler_tour(root, 0)

	# 2. If p OR q is not in the tree, then there is no LCA, return None
    if not p_found or not q_found: return None

	# 3. Find the indices of nodes p and q in the Eulerian Path       
    i, j = sorted((path.index(p), path.index(q)))   

	# 4. Find the index of the node with the smallest depth between p and q in the Eulerian Path
    k = min(range(i, j), key = lambda k: depth[k])

	# 5. The node at index k is the LCA of p and q
    return path[k]

2846. Minimum Edge Weight Equilibrium Queries in a Tree

lca新模板:

  1. adjust to same depth
  2. conservatively jump until converge