Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},
return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

題意：前序遍歷二叉樹。

思路：
1、分治的方法遞歸遍歷中左右

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }

    helper(root, res);

    return res;
}

private void helper(TreeNode node, List<Integer> res) {
    if (node == null) {
        return;
    }

    res.add(node.val);
    helper(node.left, res);
    helper(node.right, res);
}

2. 通過棧來記錄當前遍歷節(jié)點的右節(jié)點，達到中左右的遍歷效果。

    public List<Integer> preorderTraversal2(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
   
    //stack記錄右邊待遍歷的節(jié)點
    Stack<TreeNode> stack = new Stack<>();
    while (root != null) {
        res.add(root.val);
        if (root.right != null) {
            stack.add(root.right);
        }
   
        root = root.left;
        if (root == null && !stack.isEmpty()) {
            root = stack.pop();
        }
    }
   
    return res;
    }