145. Binary Tree Postorder Traversal.md

8/17/2021

145. Binary Tree Postorder Traversal

Iterative Solution Using Two Stacks

C++

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root){
            return {};
        }
        vector<int> ans;
        // stack for storing children
        stack<TreeNode*> stack1;
        // stack for storing ans
        stack<TreeNode*> stack2;
        TreeNode* cur;
        stack1.push(root);
        while(!stack1.empty()){
            cur = stack1.top();
            stack2.push(cur);
            stack1.pop();
            if(cur->left){
                stack1.push(cur->left);
            }
            if(cur->right){
                stack1.push(cur->right);
            }
            
        }
        while(!stack2.empty()){
            TreeNode* temp = stack2.top();
            ans.push_back(temp->val);
            stack2.pop();
        }
        return ans;
    }
};

Python

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return
        ans = []
        #keep track of childern nodes
        stack1 = [root]
        # keep track of solution
        stack2 = []
        while stack1:
            cur = stack1.pop()
            stack2.append(cur)
            if cur.left:
                stack1.append(cur.left)
            if cur.right:
                stack1.append(cur.right)
        while stack2:
            ans.append(stack2.pop().val)
        return ans