/**
 *	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].
 *
 *	Author: matao
 */

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

//  Definition for binary tree
class TreeNode {
  	int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 

public class BinaryTreePreorderTraversal {

	//Recursive solution
	// divide and conquer
	public static List<Integer> preorderTraversal1(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if(root == null)
            return result;
            
        result.add(root.val);
        
        List<Integer> left = preorderTraversal1(root.left);
        List<Integer> right = preorderTraversal1(root.right);
        
        result.addAll(left);
        result.addAll(right);
        return result;
    }

//--------------------------------------
    // Traverse
	public static List<Integer> preorderTraversal2(TreeNode root) {
		List<Integer> result = new ArrayList<Integer>();
		traverse(root, result);
		return result;
	}  

	public static void traverse(TreeNode root, List<Integer> result) {
		if(root == null)
			return;
		result.add(root.val);
		traverse(root.left, result);
		traverse(root.right, result);
	}
//--------------------------------------
	// Non-Recursion 
	public static List<Integer> preorderTraversal3(TreeNode root) {
		List<Integer> result = new ArrayList<Integer>();
		Stack<TreeNode> stack = new Stack<TreeNode>();
		if(root == null)
			return result;
		stack.push(root);
		while(!stack.isEmpty()) {
			TreeNode node = stack.pop();
			result.add(node.val);
			if(root.right != null) {
				stack.push(node.right);
			}
			if(root.left != null) {
				stack.push(node.left);
			}
		}
		return result;
	}  


    public static void main(String[] args) {
    	
    }
}
@@ -1585,16 +1585,17 @@
 ode%3E();%0A
+%0A
 %09%09if(roo
@@ -1596,32 +1596,34 @@
 if(root == null)
+ %7B
 %0A%09%09%09return resul
@@ -1625,16 +1625,21 @@
 result;%0A
+%09%09%7D%0A%0A
 %09%09stack.
@@ -1654,23 +1654,30 @@
 t);%0A
-%09%09
+        
 while
+ 
 (!stack.
 isEm
@@ -1676,11 +1676,9 @@
 ack.
-isE
+e
 mpty
@@ -1683,19 +1683,28 @@
 ty()) %7B%0A
-%09%09%09
+            
 TreeNode
@@ -1724,19 +1724,28 @@
 .pop();%0A
-%09%09%09
+            
 result.a
@@ -1758,26 +1758,36 @@
 e.val);%0A
-%09%09%09if(root
+            if (node
 .right !
@@ -1788,36 +1788,48 @@
 ight != null) %7B%0A
-%09%09%09%09
+                
 stack.push(node.
@@ -1840,23 +1840,42 @@
 t);%0A
-%09%09%09%7D%0A%09%09%09if(root
+            %7D%0A            if (node
 .lef
@@ -1891,12 +1891,24 @@
 ) %7B%0A
-%09%09%09%09
+                
 stac
@@ -1930,16 +1930,32 @@
 t);%0A
-%09%09%09%7D%0A%09%09%7D
+            %7D%0A        %7D%0A
 %0A%09%09r
@@ -2024,17 +2024,733 @@
 ) %7B%0A    
-%09
+/**%091%0A %09 *   %5C%0A %09 *    2%0A %09 *   /%0A %09 *  3%0A %09 */%0A    %09TreeNode root = new TreeNode(1);%0A    %09TreeNode node1 = new TreeNode(2);%0A    %09TreeNode node2 = new TreeNode(3);%0A    %09root.right = node1;%0A    %09node1.left = node2;%0A%0A    %09List%3CInteger%3E result1 = preorderTraversal1(root);%0A    %09for (Integer integer : result1) %7B%0A    %09%09System.out.print(integer + %22 %22);%0A    %09%7D%0A    %09System.out.println();%0A%0A    %09List%3CInteger%3E result2 = preorderTraversal2(root);%0A    %09for (Integer integer : result2) %7B%0A    %09%09System.out.print(integer + %22 %22);%0A    %09%7D%0A    %09System.out.println();%0A%0A    %09List%3CInteger%3E result3 = preorderTraversal3(root);%0A    %09for (Integer integer : result3) %7B%0A    %09%09System.out.print(integer + %22 %22);%0A    %09%7D%0A    %09System.out.println();
 %0A    %7D%0A%7D

add Test case