144. Binary Tree Preorder Traversal

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

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

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

---

这一题要实现二叉树的前序遍历，前序遍历的顺序是：根左右。
首先献上妇孺皆知的递归解法：

class Solution {
public:
    void work(vector<int>& ans, TreeNode* root)
    {
        if (root == NULL)
            return;
        ans.push_back(root->val);
        work(ans, root->left);
        work(ans, root->right);
    }
    vector<int> preorderTraversal(TreeNode* root)
    {
        vector<int> ans;
        work(ans, root);
        return ans;
    }
};

本代码提交AC，用时3MS。和LeetCode Binary Tree Inorder Traversal一样，本题也要实现前序遍历的迭代算法。迭代的思路同样是用堆栈来实现：首先把当前根节点压栈，然后注意，因为前序遍历是先访问左子树，后访问右子树，所以我们压栈的时候，要先压右子树，再压左子树，这样弹栈的时候才能符合前序遍历的要求。除此之外，我觉得实现起来比中序遍历要简单。
迭代版本的完整代码如下：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root)
    {
        vector<int> ans;
        if (root == NULL)
            return ans;
        stack<TreeNode*> tree;
        tree.push(root);
        TreeNode* top;
        while (!tree.empty()) {
            top = tree.top();
            ans.push_back(top->val);
            tree.pop();
            if (top->right != NULL) { // 先压栈右子树
                tree.push(top->right);
            }
            if (top->left != NULL) { // 再压栈左子树
                tree.push(top->left);
            }
        }
        return ans;
    }
};

本代码提交AC，用时也是3MS。