refactor 144

fishercoder1534 · fishercoder1534 · commit f442f512bb74 · 2020-03-01T11:51:33.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_144.java b/src/main/java/com/fishercoder/solutions/_144.java
@@ -6,6 +6,7 @@
 import java.util.ArrayList;
 import java.util.Deque;
 import java.util.List;
+import java.util.Stack;
 
 /**
  * 144. Binary Tree Preorder Traversal
@@ -26,21 +27,14 @@
 public class _144 {
   public static class Solution1 {
     public List<Integer> preorderTraversal(TreeNode root) {
-      List<Integer> list = new ArrayList();
-      if (root == null) {
-        return list;
-      }
-      Deque<TreeNode> stack = new ArrayDeque<>();
+      List<Integer> list = new ArrayList<>();
+      Stack<TreeNode> stack = new Stack<>();
       stack.push(root);
       while (!stack.isEmpty()) {
         TreeNode curr = stack.pop();
-        list.add(curr.val);
-        /**We push right nodes onto the stack first, since they'll be popped out later than
-         * the left nodes, to meet the preorder: root -> left -> right. */
-        if (curr.right != null) {
+        if (curr != null) {
+          list.add(curr.val);
           stack.push(curr.right);
-        }
-        if (curr.left != null) {
           stack.push(curr.left);
         }
       }
diff --git a/src/test/java/com/fishercoder/_144Test.java b/src/test/java/com/fishercoder/_144Test.java
@@ -1,7 +1,6 @@
 package com.fishercoder;
 
 import com.fishercoder.common.classes.TreeNode;
-import com.fishercoder.common.utils.CommonUtils;
 import com.fishercoder.common.utils.TreeUtils;
 import com.fishercoder.solutions._144;
 import org.junit.BeforeClass;
@@ -10,6 +9,8 @@
 import java.util.Arrays;
 import java.util.List;
 
+import static org.junit.Assert.assertEquals;
+
 public class _144Test {
     private static _144.Solution1 solution1;
     private static _144.Solution2 solution2;
@@ -26,15 +27,30 @@ public static void setup() {
     public void test1() {
         root = TreeUtils.constructBinaryTree(Arrays.asList(3, 1, null, null, 5, 2, null, null, 4));
         inorder = solution1.preorderTraversal(root);
-        CommonUtils.printList(inorder);
+        assertEquals(Arrays.asList(3, 1, 5, 2, 4), inorder);
     }
 
     @Test
     public void test2() {
         root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4, null, 5, 6, null, 7, null, null, null, null, 8, 9));
         TreeUtils.printBinaryTree(root);
         inorder = solution1.preorderTraversal(root);
-        CommonUtils.printList(inorder);
+        assertEquals(Arrays.asList(1, 2, 4, 7, 8, 9, 3, 5, 6), inorder);
+    }
+
+    @Test
+    public void test3() {
+        root = TreeUtils.constructBinaryTree(Arrays.asList(3, 1, null, null, 5, 2, null, null, 4));
+        inorder = solution2.preorderTraversal(root);
+        assertEquals(Arrays.asList(3, 1, 5, 2, 4), inorder);
+    }
+
+    @Test
+    public void test4() {
+        root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4, null, 5, 6, null, 7, null, null, null, null, 8, 9));
+        TreeUtils.printBinaryTree(root);
+        inorder = solution2.preorderTraversal(root);
+        assertEquals(Arrays.asList(1, 2, 4, 7, 8, 9, 3, 5, 6), inorder);
     }
 
 }
