add one more iterative solution for 144

fishercoder1534 · fishercoder1534 · commit 667fea80f02d · 2020-03-02T07:32:28.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_144.java b/src/main/java/com/fishercoder/solutions/_144.java
@@ -58,4 +58,21 @@ List<Integer> pre(TreeNode root, List<Integer> list) {
       return list;
     }
   }
+
+  public static class Solution3 {
+    public List<Integer> preorderTraversal(TreeNode root) {
+      List<Integer> list = new ArrayList<>();
+      Stack<TreeNode> stack = new Stack<>();
+      while (!stack.isEmpty() || root != null) {
+        while (root != null) {
+          list.add(root.val);
+          stack.push(root);
+          root = root.left;
+        }
+        root = stack.pop();
+        root = root.right;
+      }
+      return list;
+    }
+  }
 }
diff --git a/src/test/java/com/fishercoder/_144Test.java b/src/test/java/com/fishercoder/_144Test.java
@@ -14,13 +14,15 @@
 public class _144Test {
     private static _144.Solution1 solution1;
     private static _144.Solution2 solution2;
+    private static _144.Solution3 solution3;
     private static TreeNode root;
     private static List<Integer> inorder;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _144.Solution1();
         solution2 = new _144.Solution2();
+        solution3 = new _144.Solution3();
     }
 
     @Test
@@ -53,4 +55,20 @@ public void test4() {
         assertEquals(Arrays.asList(1, 2, 4, 7, 8, 9, 3, 5, 6), inorder);
     }
 
+    @Test
+    public void test5() {
+        root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4, null, 5, null, null, 6));
+        TreeUtils.printBinaryTree(root);
+        inorder = solution1.preorderTraversal(root);
+        assertEquals(Arrays.asList(1, 2, 4, 6, 3, 5), inorder);
+    }
+
+    @Test
+    public void test6() {
+        root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4, null, 5, null, null, 6));
+        TreeUtils.printBinaryTree(root);
+        inorder = solution3.preorderTraversal(root);
+        assertEquals(Arrays.asList(1, 2, 4, 6, 3, 5), inorder);
+    }
+
 }
