145. 二叉樹的後序遍歷

思路

在先序遍歷時，我們按照[中，左，右]的順序去輸出，為了先左再右，使用棧去反轉。
既然會[中，左，右]，那麼[中，右，左]也就呼之欲出了。
此時再把[中，右，左]整個倒轉過來，就得到後序遍歷目標的[左，右，中]了。

程式碼

1. 用 stack 倒轉

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int> res;
        stack<TreeNode*> stk;
        stack<int> collected;
        stk.push(root);
        while(!stk.empty()) {
            TreeNode* cur = stk.top(); stk.pop();
            collected.push(cur->val); // 中
            if(cur->left) stk.push(cur->left); // 左
            if(cur->right) stk.push(cur->right); // 右
        }
        while(!collected.empty()) {
            res.push_back(collected.top());
            collected.pop();
        }
        return res;
    }
};
/*
中右左 -> 左右中
*/

2. STL 直接倒轉

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int> res;
        stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty()) {
            TreeNode* cur = stk.top(); stk.pop();
            res.push_back(cur->val); // 中
            if(cur->left) stk.push(cur->left); // 左
            if(cur->right) stk.push(cur->right); // 右
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

3. 遞迴

class Solution {
private:
    void traverse(TreeNode* node, vector<int>& res) {
        if(!node) return;
        traverse(node->left, res);
        traverse(node->right, res);
        res.push_back(node->val);
    }
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        traverse(root, res);
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$