summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/main/TreeTraversal.java34
-rw-r--r--src/test/TreeTraversalTest.java28
2 files changed, 53 insertions, 9 deletions
diff --git a/src/main/TreeTraversal.java b/src/main/TreeTraversal.java
index d69164e..d7ca19d 100644
--- a/src/main/TreeTraversal.java
+++ b/src/main/TreeTraversal.java
@@ -23,7 +23,7 @@ public class TreeTraversal {
}
}
- public static class TreeOrders {
+ static class TreeOrders {
int n;
int[] key, left, right;
@@ -42,7 +42,7 @@ public class TreeTraversal {
List<Integer> inOrder() {
Stack<Integer> keyIndexStack = new Stack<>();
- ArrayList<Integer> result = new ArrayList<Integer>();
+ ArrayList<Integer> result = new ArrayList<>();
// Finish the implementation
// You may need to add a new recursive method to do that
boolean walkLeft = true;
@@ -76,7 +76,7 @@ public class TreeTraversal {
List<Integer> preOrder() {
Stack<Integer> keyIndexStack = new Stack<>();
Queue<Integer> keyIndexQueue = new LinkedList<>();
- ArrayList<Integer> result = new ArrayList<Integer>();
+ ArrayList<Integer> result = new ArrayList<>();
// Finish the implementation
// You may need to add a new recursive method to do that
boolean walkLeft = true;
@@ -113,13 +113,24 @@ public class TreeTraversal {
List<Integer> postOrder() {
Stack<Integer> keyIndexStack = new Stack<>();
- ArrayList<Integer> result = new ArrayList<Integer>();
+ HashSet<Integer> peekedSet = new HashSet<>();
+ ArrayList<Integer> result = new ArrayList<>();
+// ArrayList<Integer> bothSidesHaveBeenChecked = new ArrayList<>();
// Finish the implementation
// You may need to add a new recursive method to do that
boolean walkLeft = true;
int currentIndex = 0;
keyIndexStack.push(currentIndex);
- while (!keyIndexStack.empty() || right[currentIndex] != -1) {
+// while (!keyIndexStack.empty() || right[currentIndex] != -1) {
+ while (!keyIndexStack.empty()) {
+ if (peekedSet.contains(currentIndex)) {
+ result.add(key[currentIndex]);
+ peekedSet.remove(currentIndex);
+ keyIndexStack.pop();
+ if (keyIndexStack.empty()) break;
+ currentIndex = keyIndexStack.peek();
+ continue;
+ }
if (walkLeft) {
if (left[currentIndex] != -1) {
currentIndex = left[currentIndex];
@@ -131,18 +142,23 @@ public class TreeTraversal {
keyIndexStack.pop();
currentIndex = keyIndexStack.peek();
} else {
+ peekedSet.add(currentIndex);
currentIndex = right[currentIndex];
keyIndexStack.push(currentIndex);
}
}
} else {
if (right[currentIndex] != -1) {
+ peekedSet.add(currentIndex);
currentIndex = right[currentIndex];
keyIndexStack.push(currentIndex);
walkLeft = true;
} else {
result.add(key[currentIndex]);
- keyIndexStack.pop();
+ int i = keyIndexStack.pop();
+ if (i != currentIndex)
+ result.add(key[i]);
+ if (keyIndexStack.empty()) break;
currentIndex = keyIndexStack.peek();
}
}
@@ -156,20 +172,20 @@ public class TreeTraversal {
public void run() {
try {
new TreeTraversal().run();
- } catch (IOException e) {
+ } catch (IOException ignored) {
}
}
}, "1", 1 << 26).start();
}
- public void print(List<Integer> x) {
+ private void print(List<Integer> x) {
for (Integer a : x) {
System.out.print(a + " ");
}
System.out.println();
}
- public void run() throws IOException {
+ private void run() throws IOException {
TreeOrders tree = new TreeOrders();
tree.read();
print(tree.inOrder());
diff --git a/src/test/TreeTraversalTest.java b/src/test/TreeTraversalTest.java
index 1fd23ea..7e9773c 100644
--- a/src/test/TreeTraversalTest.java
+++ b/src/test/TreeTraversalTest.java
@@ -75,5 +75,33 @@ class TreeTraversalTest {
assertEquals(20, tt.postOrder().get(8));
assertEquals(0, tt.postOrder().get(9));
}
+ @Test
+ void test2() {
+ TreeTraversal.TreeOrders tt = new TreeTraversal.TreeOrders();
+ tt.key = new int[]{782521203, 839950857, 248660666, 696374696, 971981286};
+ tt.left = new int[]{4, -1, 3, -1, 1};
+ tt.right = new int[]{-1, -1, -1, -1, 2};
+
+ assertEquals(5, tt.inOrder().size());
+ assertEquals(839950857, tt.inOrder().get(0));
+ assertEquals(971981286, tt.inOrder().get(1));
+ assertEquals(696374696, tt.inOrder().get(2));
+ assertEquals(248660666, tt.inOrder().get(3));
+ assertEquals(782521203, tt.inOrder().get(4));
+
+ assertEquals(5, tt.preOrder().size());
+ assertEquals(782521203, tt.preOrder().get(0));
+ assertEquals(971981286, tt.preOrder().get(1));
+ assertEquals(839950857, tt.preOrder().get(2));
+ assertEquals(248660666, tt.preOrder().get(3));
+ assertEquals(696374696, tt.preOrder().get(4));
+
+ assertEquals(5, tt.postOrder().size());
+ assertEquals(839950857, tt.postOrder().get(0));
+ assertEquals(696374696, tt.postOrder().get(1));
+ assertEquals(248660666, tt.postOrder().get(2));
+ assertEquals(971981286, tt.postOrder().get(3));
+ assertEquals(782521203, tt.postOrder().get(4));
+ }
} \ No newline at end of file