binary-tree-postorder-traversa题解

我的方法是使用一个栈，由于后序遍历，因此先将右节点入栈，再将左节点入栈；然后每次判断栈顶元素，如果栈顶元素是叶子节点，则说明它要么是左节点，要么是右节点；这时候就需要判断栈顶元素的前一个元素是否为栈顶节点的爸，如果是栈顶节点的爸的话，就需要连带着他爸一起弹出；而如果是左节点的话，只需弹出他自己即可。

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