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?
Subscribe to see which companies asked this question
求一棵二叉树的先根遍历序。题目说了，递归的解法十分简单，能否用非递归的方式求解。
每遍历一个节点的时候，将右孩子入栈。向左搜索直到为空时，弹栈。
我的AC代码
public class BinaryTreePreorderTraversal {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
list.add(cur.val);
if(cur.right != null) stack.add(cur.right);
cur = cur.left;
}
if(!stack.isEmpty()) cur = stack.pop();
}
return list;
}
}LeetCode 144. Binary Tree Preorder Traversal 解题报告
原文：http://blog.csdn.net/bruce128/article/details/50716729