summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorHaidong Ji2019-01-08 21:15:27 -0600
committerHaidong Ji2019-01-08 21:15:27 -0600
commitca7416db5fb06ab354903ebd57e94cf87797becd (patch)
treedbc1b8c12a42c14edbc3a391ced1b9cb37f99e9b /src
parent926b055030fcd6f8564138819c747b97bf664954 (diff)
Tree height non-recursive version done!
Yay!!! I got rid of the recursion and used an iterative function to calculate height. The trick used was to use a queue. It turned out to be faster and consumed less memory. Fun stuff and I'm happy :)
Diffstat (limited to 'src')
-rw-r--r--src/main/TreeHeight.java80
1 files changed, 47 insertions, 33 deletions
diff --git a/src/main/TreeHeight.java b/src/main/TreeHeight.java
index 0e5119a..f21d607 100644
--- a/src/main/TreeHeight.java
+++ b/src/main/TreeHeight.java
@@ -76,8 +76,8 @@ class TreeHeight {
nodes[parentIndex].addChild(nodes[i]);
}
}
-// return treeLevelCounter(nodes, rootIndex);
- return treeLevelCounterRecursive(nodes[rootIndex]);
+ return treeLevelCounter(nodes, rootIndex);
+// return treeLevelCounterRecursive(nodes[rootIndex]);
}
private static int treeLevelCounterRecursive(Node<Integer> node) {
@@ -94,20 +94,33 @@ class TreeHeight {
}
private static int treeLevelCounter(Node<Integer>[] nodes, int rootIndex) {
- int levelCounter = 0;
+ int levelCounter = 1;
Queue<Node<Integer>> q = new LinkedList<>();
- q.add(nodes[rootIndex]);
+ int popCount = 0;
+ int childrenCount = nodes[rootIndex].getChildren().size();
+ int grandChildrenCount = 0;
+ for (int i = 0; i < childrenCount; i++) {
+ q.add(nodes[rootIndex].getChildren().get(i));
+ }
while (!q.isEmpty()) {
- Node<Integer> n = q.remove();
- int i = n.getChildren().size();
- if (i != 0) {
- for (int j = 0; j < i; j++) {
- q.add(n.getChildren().get(j));
+ if (popCount < childrenCount) {
+ Node<Integer> n = q.remove();
+ int i = n.getChildren().size();
+ if (i != 0) {
+ for (int j = 0; j < i; j++) {
+ q.add(n.getChildren().get(j));
+ }
}
+ grandChildrenCount = grandChildrenCount + i;
+ popCount = popCount + 1;
+ } else {
+ popCount = 0;
+ childrenCount = grandChildrenCount;
+ grandChildrenCount = 0;
+ levelCounter = levelCounter + 1;
}
- levelCounter = levelCounter + 1;
}
- return levelCounter;
+ return levelCounter + 1;
}
static int getHeightNaive(int[] a) {
@@ -122,28 +135,7 @@ class TreeHeight {
return maxHeight;
}
-// public static void main(String[] args) throws IOException {
-// FastScanner scanner = new FastScanner(System.in);
-// int n = scanner.nextInt();
-// int[] a = new int[n];
-// for (int i = 0; i < n; i++) {
-// a[i] = scanner.nextInt();
-// }
-// System.out.println(getHeight(a));
-// }
- public static void main(String[] args) {
- new Thread(null, new Runnable() {
- public void run() {
- try {
- runTheThing();
- } catch (IOException ignored) {
- }
- }
- }, "1", 1 << 26).start();
-
- }
-
- private static void runTheThing() throws IOException {
+ public static void main(String[] args) throws IOException {
FastScanner scanner = new FastScanner(System.in);
int n = scanner.nextInt();
int[] a = new int[n];
@@ -153,4 +145,26 @@ class TreeHeight {
System.out.println(getHeight(a));
}
+// public static void main(String[] args) {
+// new Thread(null, new Runnable() {
+// public void run() {
+// try {
+// runTheThing();
+// } catch (IOException ignored) {
+// }
+// }
+// }, "1", 1 << 26).start();
+//
+// }
+//
+// private static void runTheThing() throws IOException {
+// FastScanner scanner = new FastScanner(System.in);
+// int n = scanner.nextInt();
+// int[] a = new int[n];
+// for (int i = 0; i < n; i++) {
+// a[i] = scanner.nextInt();
+// }
+// System.out.println(getHeight(a));
+// }
+
}