-
Notifications
You must be signed in to change notification settings - Fork 0
/
Q236LowestCommonAncestorofaBinaryTree.java
67 lines (62 loc) · 1.7 KB
/
Q236LowestCommonAncestorofaBinaryTree.java
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
import util.TreeNode;
import java.util.*;
/**
* 二叉树最近公共祖先
*
* @author ahscuml
* @date 2019/4/8
* @time 19:44
*/
public class Q236LowestCommonAncestorofaBinaryTree {
/**
* 测试函数
*/
public static void main(String[] args) {
// TODO
}
/**
* 循环的方法,记录祖先
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Map<TreeNode, TreeNode> parent = new HashMap<>();
Deque<TreeNode> stack = new ArrayDeque<>();
parent.put(root, null);
stack.push(root);
while (!parent.containsKey(p) || !parent.containsKey(q)) {
TreeNode node = stack.pop();
if (node.left != null) {
parent.put(node.left, node);
stack.push(node.left);
}
if (node.right != null) {
parent.put(node.right, node);
stack.push(node.right);
}
}
Set<TreeNode> ancestors = new HashSet<>();
while (p != null) {
ancestors.add(p);
p = parent.get(p);
}
while (!ancestors.contains(q))
q = parent.get(q);
return q;
}
/**
* 递归的方法
*/
public TreeNode lowestCommonAncestorRec(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestorRec(root.left, p, q);
TreeNode right = lowestCommonAncestorRec(root.right, p, q);
if (left == null) {
return right;
}
if (right == null) {
return left;
}
return root;
}
}