Question
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?
Stats
| Adjusted Difficulty | 1 |
| Time to use | -------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
This is the easiest question of this series.
In-order and post-order are not easy at all!
Code
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new LinkedList<Integer>();
if (root == null) return ans;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
ans.add(cur.val);
// should it do reversely, right?
if (cur.right != null) stack.push(cur.right);
if (cur.left != null) stack.push(cur.left);
}
return ans;
}