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 Solution { static List<Integer> res = new ArrayList<>(); static Stack<TreeNode> stack = new Stack<>(); public static List<Integer> preorderTraversal_inStack(TreeNode root) { if(root == null) return new ArrayList<Integer>(); stack.push(root); while(!stack.isEmpty()){ TreeNode tr = stack.pop(); res.add(tr.val); if(tr.right!=null){ stack.push(tr.right); } if(tr.left!=null){ stack.push(tr.left); } } return res; }
递归法：
public static List<Integer> preorderTraversal(TreeNode root) { if(root==null) return new ArrayList<Integer>(); res.add(root.val); while(root.right!=null||root.left!=null){ preorderTraversal(root.right); preorderTraversal(root.left); } return res; }
LeetCode(144):Binary Tree Preorder Traversal
原文：http://www.cnblogs.com/rever/p/4999053.html