题目

binary-tree-postorder-traversal

算法

* 直接模拟

代码

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