8000 求树中两个节点的公共节点，第二种方法完成并且通过测试。 · ssjssh/javaalgorithm@b7cc1c8 · GitHub
[go: up one dir, main page]
Skip to content

Commit b7cc1c8

Browse files
author
shengshijun
committed
求树中两个节点的公共节点，第二种方法完成并且通过测试。
1 parent b2fbaf8 commit b7cc1c8

File tree

2 files changed

+85
-10
lines changed

2 files changed

+85
-10
lines changed

‎src/main/java/ssj/algorithm/collections/AVLTree.java

Lines changed: 70 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
package ssj.algorithm.collections;
22

33
import com.google.common.base.Preconditions;
4+
import ssj.algorithm.Queue;
45
import ssj.algorithm.SearchTree;
56
import ssj.algorithm.Stack;
67

@@ -107,7 +108,7 @@ private Node rebuildCore(T[] pre_order, int pre_start, int pre_end, T[] mid_orde
107108
}
108109

109110
/**
110-
* 求一个树中两个节点的公共节点，这是第一中方法，下面还有第二中方法
111+
* 求一个树中两个节点的公共节点，这是第一种方法。
111112
*
112113
* @param one
113114
* @param other
@@ -124,29 +125,88 @@ public T commonParent(T one, T other) {
124125
}
125126
}
126127

127-
private T getCommonParent(Node start_node, T one, T other) {
128+
/**
129+
* 求一个树中两个节点的公共节点，这是第二种方法
130+
*
131+
* @param one
132+
* @param other
133+
* @return
134+
*/
135+
public T getCommonParent(T one, T other) {
128136
Preconditions.checkNotNull(one);
129137
Preconditions.checkNotNull(other);
130-
if (start_node == null) {
131-
return null;
138+
Preconditions.checkArgument(!one.equals(other));
139+
140+
if (isEmpty()) return null;
141+
142+
Node one_node = null;
143+
Node other_node = null;
144+
Queue<Node> preorder_queue = new LinkedList<>();
145+
preorder_queue.appendTail(_head);
146+
while (!preorder_queue.isEmpty() && (one_node == null || other_node == null)) {
147+
Node cur_node = preorder_queue.removeHead();
148+
if (cur_node.getValue().equals(one)) {
149+
one_node = cur_node;
150+
} else if (cur_node.getValue().equals(other)) {
151+
other_node = cur_node;
152+
}
153+
154+
if (cur_node.getLeft() != null) {
155+
preorder_queue.appendTail(cur_node.getLeft());
156+
}
157+
158+
if (cur_node.getRight() != null) {
159+
preorder_queue.appendTail(cur_node.getRight());
160+
}
132161
}
162+
if (one_node == null || other_node == null) return null;
163+
return getCommonNode(one_node, other_node).getValue();
164+
}
133165

134-
T left_parent;
135-
if ((left_parent = getCommonParent(start_node.getLeft(), one, other)) != null) {
136-
return null;
166+
private Node getCommonNode(Node one, Node other) {
167+
Preconditions.checkArgument(other != one);
168+
int one_length = pathLength(one);
169+
int other_length = pathLength(other);
170+
while (one_length > other_length) {
171+
one = one.getParent();
172+
one_length--;
137173
}
138174

139-
T right_parent;
140-
if ((right_parent = getCommonParent(start_node.getRight(), one, other)) != null) {
141-
return null;
175+
while (one_length < other_length) {
176+
other = other.getParent();
177+
other_length--;
142178
}
143179

180+
while (one != null && other != null) {
181+
if (one.equals(other)) {
182+
return one;
183+
}
184+
one = one.getParent();
185+
other = other.getParent();
186+
}
144187
return null;
145188
}
146189

190+
/**
191+
* 计算从这个节点到根节点的距离，也就是路径长
192+
*
193+
* @param node
194+
* @return
195+
*/
196+
private int pathLength(Node node) {
197+
Preconditions.checkNotNull(node);
198+
int result = 0;
199+
while (node != null) {
200+
result++;
201+
node = node.getParent();
202+
}
203+
return result;
204+
}
205+
147206
private Node getCommonNode(Stack<Node> one, Stack<Node> other) {
148207
Preconditions.checkNotNull(one);
149208
Preconditions.checkNotNull(other);
209+
Preconditions.checkArgument(!one.equals(other));
150210
if (one.isEmpty() || other.isEmpty()) {
151211
return null;
152212
}

‎src/test/java/ssj/algorithm/collections/AVLTreeTest.java

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -186,4 +186,19 @@ public void testCommonParent() {
186186
assertTrue(tree.commonParent(9, 4).equals(6));
187187
assertTrue(tree.commonParent(16, 11).equals(14));
188188
}
189+
190+
@Test
191+
public void testGetCommonParent() {
192+
int[] tree_data = new int[]{10, 4, 6, 14, 4, 8, 9, 12, 16, 11};
193+
AVLTree<Integer> tree = new AVLTree<>();
194+
assertTrue(tree.commonParent(4, 8) == null);
195+
for (int i : tree_data) {
196+
tree.add(i);
197+
}
198+
//这个测试依赖于树的实现，并不通用
199+
assertTrue(tree.getCommonParent(4, 8).equals(6));
200+
assertTrue(tree.getCommonParent(9, 11).equals(10));
201+
assertTrue(tree.getCommonParent(9, 4).equals(6));
202+
assertTrue(tree.getCommonParent(16, 11).equals(14));
203+
}
189204
}

0 commit comments

Comments
 (0)
0