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?
SOLUTION1&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 // sol1: 12 public List<Integer> preorderTraversal1(TreeNode root) { 13 List<Integer> ret = new ArrayList<Integer>(); 14 15 rec(root, ret); 16 return ret; 17 } 18 19 public void rec(TreeNode root, List<Integer> ret) { 20 if (root == null) { 21 return; 22 } 23 24 ret.add(root.val); 25 rec(root.left, ret); 26 rec(root.right, ret); 27 } 28 29 public List<Integer> preorderTraversal(TreeNode root) { 30 List<Integer> ret = new ArrayList<Integer>(); 31 32 if (root == null) { 33 return ret; 34 } 35 36 Stack<TreeNode> s = new Stack<TreeNode>(); 37 s.push(root); 38 39 while (!s.isEmpty()) { 40 TreeNode cur = s.pop(); 41 ret.add(cur.val); 42 43 if (cur.right != null) { 44 s.push(cur.right); 45 } 46 47 if (cur.left != null) { 48 s.push(cur.left); 49 } 50 } 51 52 return ret; 53 } 54 }
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/tree/PreorderTraversal.java
LeetCode: Binary Tree Preorder Traversal 解题报告
原文:http://www.cnblogs.com/yuzhangcmu/p/4141530.html