這個(gè)系列有preorder inorder postorder三題，考點(diǎn)都不是遞歸，而是迭代。迭代挺難想的，尤其是外面的while循環(huán)。這題的迭代寫(xiě)法我模仿inorder寫(xiě)出來(lái)了，一步步在紙上模擬入棧出棧就好了。

RECURSION:

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

    private List<Integer> dfs(TreeNode root, List<Integer> res) {
        if (root == null) {
            return res;
        }
        res.add(root.val);
        dfs(root.left, res);
        dfs(root.right, res);
        return res;
    }

ITERATION:

public List<Integer> preorderTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<>();
    Stack<TreeNode> s = new Stack<>();
    while (!s.isEmpty() || root!=null) {
        if (root != null) {
            res.add(root.val);
            s.push(root);
            root = root.left;
        }else {
            TreeNode node = s.pop();
            root = node.right;
        }
    }
    return res;
}

看了下discussion，很多跟我寫(xiě)的都不一樣，說(shuō)明迭代寫(xiě)法確實(shí)比遞歸寫(xiě)法多，按照自己的思路來(lái)就好。