@@ -0,0 +1,1940 @@
+/**%0A *%09Given a binary tree, return the preorder traversal of its nodes' values.%0A *%0A *%09For example:%0A *%09Given binary tree %7B1,#,2,3%7D,%0A *  1%0A *   %5C%0A *    2%0A *   /%0A *  3%0A *%09return %5B1,2,3%5D.%0A *%0A *%09Author: matao%0A */%0A%0Aimport java.util.ArrayList;%0Aimport java.util.Stack;%0Aimport java.util.List;%0A%0A//  Definition for binary tree%0Aclass TreeNode %7B%0A  %09int val;%0A    TreeNode left;%0A    TreeNode right;%0A    TreeNode(int x) %7B val = x; %7D%0A%7D%0A %0A%0Apublic class BinaryTreePreorderTraversal %7B%0A%0A%09//Recursive solution%0A%09// divide and conquer%0A%09public static List%3CInteger%3E preorderTraversal1(TreeNode root) %7B%0A        List%3CInteger%3E result = new ArrayList%3CInteger%3E();%0A        if(root == null)%0A            return result;%0A            %0A        result.add(root.val);%0A        %0A        List%3CInteger%3E left = preorderTraversal1(root.left);%0A        List%3CInteger%3E right = preorderTraversal1(root.right);%0A        %0A        result.addAll(left);%0A        result.addAll(right);%0A        return result;%0A    %7D%0A%0A//--------------------------------------%0A    // Traverse%0A%09public static List%3CInteger%3E preorderTraversal2(TreeNode root) %7B%0A%09%09List%3CInteger%3E result = new ArrayList%3CInteger%3E();%0A%09%09traverse(root, result);%0A%09%09return result;%0A%09%7D  %0A%0A%09public static void traverse(TreeNode root, List%3CInteger%3E result) %7B%0A%09%09if(root == null)%0A%09%09%09return;%0A%09%09result.add(root.val);%0A%09%09traverse(root.left, result);%0A%09%09traverse(root.right, result);%0A%09%7D%0A//--------------------------------------%0A%09// Non-Recursion %0A%09public static List%3CInteger%3E preorderTraversal3(TreeNode root) %7B%0A%09%09List%3CInteger%3E result = new ArrayList%3CInteger%3E();%0A%09%09Stack%3CTreeNode%3E stack = new Stack%3CTreeNode%3E();%0A%09%09if(root == null)%0A%09%09%09return result;%0A%09%09stack.push(root);%0A%09%09while(!stack.isEmpty()) %7B%0A%09%09%09TreeNode node = stack.pop();%0A%09%09%09result.add(node.val);%0A%09%09%09if(root.right != null) %7B%0A%09%09%09%09stack.push(node.right);%0A%09%09%09%7D%0A%09%09%09if(root.left != null) %7B%0A%09%09%09%09stack.push(node.left);%0A%09%09%09%7D%0A%09%09%7D%0A%09%09return result;%0A%09%7D  %0A%0A%0A    public static void main(String%5B%5D args) %7B%0A    %09%0A    %7D%0A%7D

add Binary Tree Preorder Traversal solution