Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes‘ values.
1
/ 2 3
/ 4 5
return [1,2,4,5,3].
Can you do it without recursion?
前序遍历两种方式，递归与非递归方式。
首先要明确前序遍历，顺序是先父节点，然后左子节点，右子节点。
The key to solve this problem is to understand the following:
使用递归的方法：
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: Preorder in ArrayList which contains node values. */ ArrayList<Integer> list=new ArrayList<Integer>(); public ArrayList<Integer> preorderTraversal(TreeNode root) { // write your code here if(root!=null) { helper(root); } return list; } public void helper(TreeNode p) { list.add(p.val); if(p.left!=null) { helper(p.left); } if(p.right!=null) { helper(p.right); } } }
非递归：
The key to solve this problem is using a stack to store left and right children, and push right child first so that it is processed after the left child.
public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { public ArrayList<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> list = new ArrayList<Integer>(); if(root == null) return list; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); while(!stack.empty()){ TreeNode cur= stack.pop(); list.add(cur.val); if(cur.right != null){ stack.push(cur.right); } if(n.left != null){ stack.push(cur.left); } } return list; } }
Keep in mind that stack is a FILO data type, so when we process the data, we need to push the right children first, and then left children.
[lintcode easy]Binary Tree Preorder Traversal
原文：http://www.cnblogs.com/kittyamin/p/4970590.html