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].
二叉树的前序遍历，根节点→左子树→右子树
解题思路一：
递归实现，JAVA实现如下：
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if (root == null)
return list;
list.add(root.val);
list.addAll(preorderTraversal(root.left));
list.addAll(preorderTraversal(root.right));
return list;
}
解题思路二：
使用stack实现，JAVA实现如下：
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if (root == null)
return list;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
TreeNode pop = root;
while (!stack.isEmpty()) {
pop = stack.pop();
list.add(pop.val);
if (pop.right != null)
stack.add(pop.right);
if (pop.left != null)
stack.add(pop.left);
}
return list;
}
Java for LeetCode 144 Binary Tree Preorder Traversal
原文：http://www.cnblogs.com/tonyluis/p/4553030.html