递归

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

非递归

首先确定 node 指针的“轨迹”

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        TreeNode* pre = nullptr;
        while (root || !st.empty()) {
            if (root) {
                st.push(root);
                root = root->left;
            } else {
                root = st.top();
                st.pop();
                if (!root->right || root->right == pre) {
                    res.push_back(root->val);
                    pre = root;
                    root = nullptr;
                } else {
                    st.push(root);
                    root = root->right;
                }
            }
        }
        return res;
    }
};

另一种偷巧的方法 - 2次反转

左 右 根 <--> 根 右 左 （先序遍历通过左右孩子入栈顺序得到）

下面是对应的两套写法

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        if (!root) return {};
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            res.push_back(node->val);
            if (node->left) st.push(node->left); // 第一次翻转
            if (node->right) st.push(node->right); // 更改入栈循序，先访问右
        }
        reverse(res.begin(), res.end()); // 第二次翻转
        return res;
    }
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        // postorder: left right root <--> preorder' : root right left
        vector<int> res;
        stack<TreeNode*> st;
        while (root || !st.empty()) {
            if (root) {
                res.push_back(root->val);
                st.push(root);
                root = root->right;
            } else {
                root = st.top();
                st.pop();
                root = root->left;
            }
        }
        reverse(res.begin(), res.end());
        return res;;
    }
};