package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**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_original(TreeNode root) {
        List<Integer> list = new ArrayList();
        Stack<TreeNode> stack = new Stack();
        if(root == null) return list;
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode curr = stack.pop();
            list.add(curr.val);
            if(curr.right != null) stack.push(curr.right);
            if(curr.left != null) stack.push(curr.left);
        }
        return list;
    }

    public List<Integer> preorderTraversal_recursive_1(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;
    }


	public List<Integer> preorderTraversal_recursive_2(TreeNode root) {
		List<Integer> result = new ArrayList();
		if (root != null) dfs(root, result);
		return result;
	}

	private void dfs(TreeNode root, List<Integer> result){
		result.add(root.val);
		if (root.left != null) dfs(root.left, result);
		if (root.right != null) dfs(root.right, result);
	}


}

@@ -99,70 +99,58 @@
 til.
-ArrayList;%0Aimport java.util.List;%0Aimport java.util.Stack;%0A%0A/**
+*;%0A%0A/**%0A * 144. Binary Tree Preorder Traversal%0A * 
 Give
@@ -390,16 +390,17 @@
  _144 %7B%0A
+%0A
     publ
@@ -447,17 +447,8 @@
 tive
-_original
 (Tre
@@ -519,81 +519,88 @@
     
-Stack%3CTreeNode%3E stack = new Stack();%0A        if(root == null) return list
+if(root == null) return list;%0A        Deque%3CTreeNode%3E stack = new ArrayDeque%3C%3E()
 ;%0A  
@@ -725,24 +725,199 @@
 (curr.val);%0A
+            /**We push right nodes onto the stack first, since they'll be popped out later than%0A             * the left nodes, to meet the preorder: root -%3E left -%3E right. */%0A
             
@@ -1110,18 +1110,16 @@
 ecursive
-_1
 (TreeNod
@@ -1434,363 +1434,6 @@
  %7D%0A%0A
-%0A%09public List%3CInteger%3E preorderTraversal_recursive_2(TreeNode root) %7B%0A%09%09List%3CInteger%3E result = new ArrayList();%0A%09%09if (root != null) dfs(root, result);%0A%09%09return result;%0A%09%7D%0A%0A%09private void dfs(TreeNode root, List%3CInteger%3E result)%7B%0A%09%09result.add(root.val);%0A%09%09if (root.left != null) dfs(root.left, result);%0A%09%09if (root.right != null) dfs(root.right, result);%0A%09%7D%0A%0A%0A
 %7D%0A

edit 144