add accepted solution for 1104 and tests

fishercoder1534 · fishercoder1534 · commit 298dfb2c2b76 · 2020-02-10T09:23:17.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_1104.java b/src/main/java/com/fishercoder/solutions/_1104.java
@@ -1,10 +1,11 @@
 package com.fishercoder.solutions;
 
 import com.fishercoder.common.classes.TreeNode;
+import com.fishercoder.common.utils.CommonUtils;
 import com.fishercoder.common.utils.TreeUtils;
 
-import java.lang.reflect.Array;
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Collections;
 import java.util.Deque;
 import java.util.LinkedList;
@@ -36,6 +37,7 @@ public static class Solution1 {
         /**This brute force solution is correct but results in TLE on LeetCode.*/
         public List<Integer> pathInZigZagTree(int label) {
             Deque<Integer> deque = buildZigZagOrderList(label);
+            CommonUtils.printDeque(deque);
             TreeNode root = buildZigZagOrderTree(deque);
             TreeUtils.printBinaryTree(root);
             return dfs(root, label, new ArrayList<>());
@@ -97,4 +99,55 @@ private Deque<Integer> buildZigZagOrderList(int label) {
             return deque;
         }
     }
+
+    public static class Solution2 {
+        /**We'll directly compute the index of its parent, it'll be much faster this way.*/
+        public List<Integer> pathInZigZagTree(int label) {
+            List<List<Integer>> lists = buildZigZagOrderList(label);
+            CommonUtils.printListList(lists);
+            List<Integer> result = new ArrayList<>();
+            int index = findIndex(lists.get(lists.size() - 1), label);
+            result.add(label);
+            for (int i = lists.size() - 2; i >= 0; i--) {
+                index /= 2;
+                result.add(lists.get(i).get(index));
+            }
+            Collections.sort(result);
+            return result;
+        }
+
+        private int findIndex(List<Integer> level, int label) {
+            for (int i = 0; i < level.size(); i++) {
+                if (level.get(i) == label) {
+                    return i;
+                }
+            }
+            return -1;
+        }
+
+        private List<List<Integer>> buildZigZagOrderList(int label) {
+            List<List<Integer>> lists = new ArrayList<>();
+            int num = 1;
+            int level = 2;
+            lists.add(Arrays.asList(num));
+            if (label == 1) {
+                return lists;
+            }
+            List<Integer> newLevel = new ArrayList<>();
+            do {
+                newLevel.clear();
+                num++;
+                for (; num < Math.pow(2, level); num++) {
+                    newLevel.add(num);
+                }
+                num--;
+                if (level % 2 == 0) {
+                    Collections.reverse(newLevel);
+                }
+                lists.add(new ArrayList<>(newLevel));
+                level++;
+            } while (newLevel.get(0) < label && newLevel.get(newLevel.size() - 1) < label);
+            return lists;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_1104Test.java b/src/test/java/com/fishercoder/_1104Test.java
@@ -12,11 +12,13 @@
 
 public class _1104Test {
     private static _1104.Solution1 solution1;
+    private static _1104.Solution2 solution2;
     private static List<Integer> expected;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _1104.Solution1();
+        solution2 = new _1104.Solution2();
     }
 
     @Test
@@ -81,4 +83,22 @@ public void test9() {
         assertEquals(expected, solution1.pathInZigZagTree(500000));
     }
 
+    @Test
+    public void test10() {
+        expected = Arrays.asList(1);
+        assertEquals(expected, solution1.pathInZigZagTree(1));
+    }
+
+    @Test
+    public void test11() {
+        expected = Arrays.asList(1, 3, 4, 14);
+        assertEquals(expected, solution2.pathInZigZagTree(14));
+    }
+
+    @Test
+    public void test12() {
+        expected = Arrays.asList(1);
+        assertEquals(expected, solution2.pathInZigZagTree(1));
+    }
+
 }
