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?
Solution 1: 非递归
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public List<Integer> preorderTraversal(TreeNode root) { 12 List<Integer> result=new ArrayList<Integer>(); 13 if(root==null){ 14 return result; 15 } 16 Stack<TreeNode> s=new Stack<TreeNode>(); 17 result.add(root.val); 18 s.add(root); 19 TreeNode p=root.left; 20 21 while(!s.isEmpty()){ 22 while(p!=null){ 23 s.add(p); 24 result.add(p.val); 25 p=p.left; 26 } 27 TreeNode n=s.pop(); 28 p=n.right; 29 if(p!=null){ 30 s.add(p); 31 result.add(p.val); 32 p=p.left; 33 } 34 } 35 return result; 36 } 37 }
Solution 2: 递归
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public List<Integer> preorderTraversal(TreeNode root) { 12 List<Integer> result=new ArrayList<Integer>(); 13 myPreorderTraversal(root,result); 14 return result; 15 } 16 17 private void myPreorderTraversal(TreeNode root, List<Integer> result) { 18 // TODO Auto-generated method stub 19 if(root!=null){ 20 result.add(root.val); 21 myPreorderTraversal(root.left, result); 22 myPreorderTraversal(root.right, result); 23 } 24 } 25 }
[Leetcode] Binary Tree Preorder Traversal
原文：http://www.cnblogs.com/Phoebe815/p/4042914.html