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

Commit b2fbaf8

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

File tree

2 files changed

+99
-8
lines changed

2 files changed

+99
-8
lines changed

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

Lines changed: 83 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -106,6 +106,82 @@ private Node rebuildCore(T[] pre_order, int pre_start, int pre_end, T[] mid_orde
106106
return null;
107107
}
108108

109+
/**
110+
* 求一个树中两个节点的公共节点，这是第一中方法，下面还有第二中方法
111+
*
112+
* @param one
113+
* @param other
114+
* @return
115+
*/
116+
public T commonParent(T one, T other) {
117+
Preconditions.checkNotNull(one);
118+
Preconditions.checkNotNull(other);
119+
if (isEmpty()) {
120+
return null;
121+
} else {
122+
Node result = getCommonNode(getNodePath(one), getNodePath(other));
123+
return (result == null) ? null : result.getValue();
124+
}
125+
}
126+
127+
private T getCommonParent(Node start_node, T one, T other) {
128+
Preconditions.checkNotNull(one);
129+
Preconditions.checkNotNull(other);
130+
if (start_node == null) {
131+
return null;
132+
}
133+
134+
T left_parent;
135+
if ((left_parent = getCommonParent(start_node.getLeft(), one, other)) != null) {
136+
return null;
137+
}
138+
139+
T right_parent;
140+
if ((right_parent = getCommonParent(start_node.getRight(), one, other)) != null) {
141+
return null;
142+
}
143+
144+
return null;
145+
}
146+
147+
private Node getCommonNode(Stack<Node> one, Stack<Node> other) {
148+
Preconditions.checkNotNull(one);
149+
Preconditions.checkNotNull(other);
150+
if (one.isEmpty() || other.isEmpty()) {
151+
return null;
152+
}
153+
Node last_common_node = null;
154+
Node last_node;
155+
while (!one.isEmpty() && !other.isEmpty() && (last_node = one.pop()).equals(other.pop())) {
156+
last_common_node = last_node;
157+
}
158+
return last_common_node;
159+
}
160+
161+
162+
private Stack<Node> getNodePath(T ele) {
163+
Preconditions.checkNotNull(ele);
164+
Stack<Node> stack = new LinkedStack<>();
165+
if (!isEmpty()) {
166+
getNodePathCore(_head, ele, stack);
167+
}
168+
return stack;
169+
}
170+
171+
private boolean getNodePathCore(Node start, T ele, Stack<Node> path_stack) {
172+
Preconditions.checkNotNull(ele);
173+
Preconditions.checkNotNull(path_stack);
174+
if (start == null) {
175+
return false;
176+
}
177+
if (start.getValue().equals(ele) || getNodePathCore(start.getLeft(), ele, path_stack) || getNodePathCore(start.getRight(), ele, path_stack)) {
178+
path_stack.push(start);
179+
return true;
180+
}
181+
182+
return false;
183+
}
184+
109185

110186
private Vector<LinkedList<Node>> createLevelLinkedList() {
111187
Vector<LinkedList<Node>> result = new Vector<>();
@@ -515,15 +591,15 @@ public Node(Node left, Node parent, Node right) {
515591

516592
@Override
517593
public String toString() {
518-
final StringBuilder sb = new StringBuilder("\tNode{");
594+
final StringBuilder sb = new StringBuilder("Node{");
519595
sb.append("height=").append(height);
520596
sb.append(", value=").append(value);
521-
if (left != null) {
522-
sb.append(",\n\t left=").append(left);
523-
}
524-
if (right != null) {
525-
sb.append(",\n\t right=").append(right);
526-
}
597+
// if (left != null) {
598+
// sb.append(",\n\t left=").append(left);
599+
// }
600+
// if (right != null) {
601+
// sb.append(",\n\t right=").append(right);
602+
// }
527603
sb.append('}');
528604
return sb.toString();
529605
}

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

Lines changed: 16 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -167,8 +167,23 @@ public void testPathIterator() {
167167
tree.add(i);
168168
}
169169
Iterator<LinkedList<Integer>> iterator = tree.pathIterator();
170-
while (iterator.hasNext()){
170+
while (iterator.hasNext()) {
171171
System.out.println(iterator.next());
172172
}
173173
}
174+
175+
@Test
176+
public void testCommonParent() {
177+
int[] tree_data = new int[]{10, 4, 6, 14, 4, 8, 9, 12, 16, 11};
178+
AVLTree<Integer> tree = new AVLTree<>();
179+
assertTrue(tree.commonParent(4, 8) == null);
180+
for (int i : tree_data) {
181+
tree.add(i);
182+
}
183+
//这个测试依赖于树的实现，并不通用
184+
assertTrue(tree.commonParent(4, 8).equals(6));
185+
assertTrue(tree.commonParent(9, 11).equals(10));
186+
assertTrue(tree.commonParent(9, 4).equals(6));
187+
assertTrue(tree.commonParent(16, 11).equals(14));
188+
}
174189
}

0 commit comments

Comments
 (0)
0