Question

link

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;
}