package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;


/**
 * 144. Binary Tree Preorder Traversal
 * Given a binary tree, return the preorder traversal of its nodes' values.

 For example:
 Given binary tree {1,#,2,3},
 1
  \
   2
  /
 3
 return [1,2,3].

 Note: Recursive solution is trivial, could you do it iteratively?*/

public class _144 {

    public List<Integer> preorderTraversal_iterative(TreeNode root) {
        List<Integer> list = new ArrayList();
        if (root == null) {
            return list;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        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) {
                stack.push(curr.right);
            }
            if (curr.left != null) {
                stack.push(curr.left);
            }
        }
        return list;
    }

    public List<Integer> preorderTraversal_recursive(TreeNode root) {
        List<Integer> list = new ArrayList();
        return pre(root, list);
    }

    List<Integer> pre(TreeNode root, List<Integer> list) {
        if (root == null) {
            return list;
        }
        list.add(root.val);
        pre(root.left, list);
        pre(root.right, list);
        return list;
    }

}

@@ -183,17 +183,16 @@
 .List;%0A%0A
-%0A
 /**%0A * 1
@@ -226,18 +226,17 @@
 aversal%0A
- *
+%0A
  Given a
@@ -473,16 +473,49 @@
  _144 %7B%0A
+  public static class Solution1 %7B
 %0A    pub
@@ -553,18 +553,8 @@
 rsal
-_iterative
 (Tre
@@ -565,34 +565,32 @@
 e root) %7B%0A      
- 
- 
 List%3CInteger%3E li
@@ -613,26 +613,24 @@
 st();%0A      
-  
 if (root == 
@@ -637,36 +637,32 @@
 null) %7B%0A        
-   
- 
 return list;%0A   
@@ -660,30 +660,26 @@
 list;%0A      
-  %7D%0A  
+%7D%0A
       Deque%3C
@@ -718,26 +718,24 @@
 %3C%3E();%0A      
-  
 stack.push(r
@@ -736,26 +736,24 @@
 push(root);%0A
-  
       while 
@@ -781,20 +781,16 @@
         
-  
-  
 TreeNode
@@ -814,28 +814,24 @@
 ();%0A        
-   
- 
 list.add(cur
@@ -834,28 +834,24 @@
 (curr.val);%0A
-    
         /**W
@@ -939,20 +939,16 @@
         
-    
 * the le
@@ -1005,36 +1005,32 @@
 ght. */%0A        
-  
-  
 if (curr.right !
@@ -1041,38 +1041,32 @@
 ll) %7B%0A          
-      
 stack.push(curr.
@@ -1077,34 +1077,26 @@
 t);%0A        
-   
- 
 %7D%0A
-    
         if (
@@ -1112,30 +1112,24 @@
  != null) %7B%0A
-      
           st
@@ -1157,28 +1157,24 @@
         
-    
 %7D%0A      
   %7D%0A    
@@ -1161,30 +1161,26 @@
     %7D%0A      
-  %7D%0A  
+%7D%0A
       return
@@ -1188,24 +1188,62 @@
 list;%0A    %7D%0A
+  %7D%0A%0A  public static class Solution2 %7B
 %0A    public 
@@ -1277,18 +1277,8 @@
 rsal
-_recursive
 (Tre
@@ -1287,26 +1287,24 @@
 ode root) %7B%0A
-  
       List%3CI
@@ -1331,26 +1331,24 @@
 rrayList();%0A
-  
       return
@@ -1433,26 +1433,24 @@
 st) %7B%0A      
-  
 if (root == 
@@ -1453,28 +1453,24 @@
  == null) %7B%0A
-    
         retu
@@ -1480,30 +1480,26 @@
 list;%0A      
-  %7D%0A  
+%7D%0A
       list.a
@@ -1510,34 +1510,32 @@
 oot.val);%0A      
- 
- 
 pre(root.left, l
@@ -1536,26 +1536,24 @@
 eft, list);%0A
-  
       pre(ro
@@ -1565,26 +1565,24 @@
 ght, list);%0A
-  
       return
@@ -1594,11 +1594,14 @@
 ;%0A    %7D%0A
+  %7D
 %0A%7D%0A

refactor 144