145. Binary Tree Postorder Traversal

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

Example:

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

Output: [3,2,1]

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

void helper(TreeNode* root, vector<int>& res) {
    if (!root) return;
    helper(root->left, res);
    helper(root->right, res);
    res.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) { // time: O(n); space: O(n)
    vector<int> res;
    helper(root, res);
    return res;
}

Iteration的解法先照著根->右->左的順序掃描最後再反轉順序成左->右->根。

vector<int> postorderTraversal(TreeNode* root) { // time: O(n); space: O(n)
    vector<int> res;
    if (!root) return res;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* cur = st.top(); st.pop();
        res.push_back(cur->val);
        if (cur->left) st.push(cur->left);
        if (cur->right) st.push(cur->right);
    }
    reverse(res.begin(), res.end());
    return res;
}

94. Binary Tree Inorder Traversal

144. Binary Tree Preorder Traversal