-
Notifications
You must be signed in to change notification settings - Fork 0
/
LowestAncestor.java
167 lines (144 loc) · 4.9 KB
/
LowestAncestor.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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
package basic.binarytree;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
/**
* 给定一个二叉树的头节点,和另外两个节点a、b,返回a、b的最低公共祖先。
* <p>
* 最低公共祖先:a、b往上找,第一个相同的祖先(这个公共祖先也可能是a或b自己)
* <p>
* 微信公众号:Java和算法学习
*
* @author 周一
*/
public class LowestAncestor {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
}
public static Node lowestAncestor(Node head, Node a, Node b) {
if (head == null) {
return null;
}
return process(head, a, b).answer;
}
public static class Info {
public boolean findA;
public boolean findB;
public Node answer;
public Info(boolean findA, boolean findB, Node answer) {
this.findA = findA;
this.findB = findB;
this.answer = answer;
}
}
public static Info process(Node x, Node a, Node b) {
if (x == null) {
return new Info(false, false, null);
}
// 获取左右子树的信息
Info leftInfo = process(x.left, a, b);
Info rightInfo = process(x.right, a, b);
// 拼凑自己的信息
// 不要忽略了自己是a或b的情况
boolean findA = leftInfo.findA || rightInfo.findA || x == a;
boolean findB = leftInfo.findB || rightInfo.findB || x == b;
Node answer = null;
if (leftInfo.answer != null) {
// 左树中有答案,则此答案就是最终的答案
answer = leftInfo.answer;
} else if (rightInfo.answer != null) {
// 右树中有答案,则此答案就是最终的答案
answer = rightInfo.answer;
} else {
// 左树和右树都没有答案,但是找到了a和b,则答案就是当前节点X
if (findA && findB) {
answer = x;
}
}
return new Info(findA, findB, answer);
}
public static Node comparator(Node head, Node a, Node b) {
if (head == null) {
return null;
}
// key的父节点是value
Map<Node, Node> parentMap = new HashMap<>(16);
parentMap.put(head, null);
setParentMap(head, parentMap);
Set<Node> aSet = new HashSet<>();
aSet.add(a);
Node current = a;
while (current != null) {
aSet.add(parentMap.get(current));
current = parentMap.get(current);
}
current = b;
while (!aSet.contains(current)) {
current = parentMap.get(current);
}
return current;
}
private static void setParentMap(Node head, Map<Node, Node> parentMap) {
if (head.left != null) {
parentMap.put(head.left, head);
setParentMap(head.left, parentMap);
}
if (head.right != null) {
parentMap.put(head.right, head);
setParentMap(head.right, parentMap);
}
}
public static void main(String[] args) {
int maxLevel = 6;
int maxValue = 1000;
int testTimes = 100000;
for (int i = 0; i < testTimes; i++) {
Node head = generateRandomBinaryTree(maxLevel, maxValue);
Node a = getRandomOne(head);
Node b = getRandomOne(head);
if (lowestAncestor(head, a, b) != comparator(head, a, b)) {
System.out.println("Error");
break;
}
}
System.out.println("Finish");
}
// ----------------------------------- 辅助测试的方法 ---------------------------------
public static Node generateRandomBinaryTree(int maxLevel, int maxValue) {
return generate(1, maxLevel, maxValue);
}
private static Node generate(int level, int maxLevel, int maxValue) {
if (level > maxLevel || Math.random() < 0.2) {
return null;
}
Node head = new Node((int) ((maxValue + 1) * Math.random()));
head.left = generate(level + 1, maxLevel, maxValue);
head.right = generate(level + 1, maxLevel, maxValue);
return head;
}
public static Node getRandomOne(Node head) {
if (head == null) {
return null;
}
List<Node> list = new ArrayList<>();
setBinaryTreeToList(head, list);
int randomIndex = (int) (list.size() * Math.random());
return list.get(randomIndex);
}
private static void setBinaryTreeToList(Node head, List<Node> list) {
if (head == null) {
return;
}
list.add(head);
setBinaryTreeToList(head.left, list);
setBinaryTreeToList(head.right, list);
}
}