First Common Ancestor: Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.
Hints: #10, #16, #28, #36, #46, #70, #80, #96
解法1
二叉树任意两节点的第一个共同祖先，假设每个node都有一个parent指针。
暴力的做法是：
- 从node A出发往下递归找node B，如果找到了则node A就是node B的祖先
- 没找到，从node A的parent出发往下滴贵找node B，如果找到了则node A的parent是node B的共同祖先
- 没找到，从node A的parent的parent，。。。
- 。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public Node findAncestor(Node parent, Node b) {
if (parent == null) {
// 说明这两个不在一颗树里
return null;
}
if (contains(parent, b)) {
return parent;
}
return findAncestor(parent.parent, b);
}
// 判断这个node及其所有子孙是否含有target node。
public boolean contains(Node node, Node target) {
if (node == null) {
return false;
}
if (node == target) {
return true;
}
if (node.left == target || node.right == target) {
return true;
}
return contains(node.left, target) || contains(node.right, target);
}
|
时间复杂度：O(n^2)，试想a、b两个节点分别在一颗树的最左和最右两端。
解法2
解法1中有一些重复计算，所以它时O(n^2)，比如下面在2这个子树没有找到的情况下，上升到1时，在从1往下找的时候不需要再到2里找一遍，而应该只找3。
1
2
3
4
5
|
1
/ \
2 3
/ \
4 5
|
代码：
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
|
findAncestor(a, b, null);
public Node findAncestor(Node parent, Node b, Exclusion exclusion) {
if (parent == null) {
// 说明这两个不在一颗树里
return null;
}
if (parent == b) {
return parent;
}
if (exclusion == LEFT) {
if (contains(parent.right, b)) {
return parent;
}
} else if (exclusion == RIGHT) {
if (contains(parent.left, b)) {
return parent;
}
} else {
if (contains(parent, b)) {
return parent;
}
}
if (parent.parent != null && parent == parent.parent.left) {
return findAncestor(parent.parent, b, Exclusion.LEFT);
}
if (parent.parent != null && parent == parent.parent.right) {
return findAncestor(parent.parent, b, Exclusion.RIGHT);
}
return null;
}
// 判断这个node及其所有子孙是否含有target node。
public boolean contains(Node node, Node target) {
if (node == null) {
return false;
}
if (node == target) {
return true;
}
if (node.left == target || node.right == target) {
return true;
}
return contains(node.left, target) || contains(node.right, target);
}
|
时间复杂度：O(n)
解法3
如果可以拿到parent，那么这个问题就和2.7-intersection有点像了：从两个节点出发，沿着parent链表一路走到底，找到第一个交叉点，这个交叉点就是共同祖先。
解法4
在没有parent指针的情况下怎么弄？
共同祖先有什么特性：
1
2
3
4
5
|
p
/ \
x b
/ \
a x
|
p是a、b的第一个共同祖先，a、b分别在p的左右两边
a就是a、b的第一个共同祖先，a、b在一边。
所以共同祖先p有两个特性：
- a、b在p的左右两边
- 或者p == a || p == b
我们先从root开始，判断上面的两个特性是否成立，如果不成立，那么就下沉到左边or右边继续这个过程。
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
|
public Node findAncestor(Node root, Node a, Node b) {
if (root == a || root == b) {
return root;
}
boolean aLeft = contains(root.left, a);
boolean bLeft = contains(root.left, b);
if (aLeft xor bLeft) {
return root;
}
if (aleft && bLeft) {
return findAncestor(root.left, a, b);
}
return findAncestor(root.right, a, b);
}
// 判断这个node及其所有子孙是否含有target node。
public boolean contains(Node node, Node target) {
if (node == null) {
return false;
}
if (node == target) {
return true;
}
if (node.left == target || node.right == target) {
return true;
}
return contains(node.left, target) || contains(node.right, target);
}
|
评论