0145. Postorder Traversal

Easy | Tree + Traversal | 20 ms (99.24%), 14.1 MB (91.99%)

❓ Problem Statement

Source: LeetCode - Binary Tree Postorder Traversal GitHub: Solution / Performance

Given the root of a binary tree, return the postorder traversal of its nodes' values.

✍🏻 Constraints & Example

Constraints:

• The number of the nodes in the tree is in the range [0, 100].

• -100 <= Node.val <= 100

💡 Ideas

Postorder traversal stops iterating when there is no left-child node.

In other words, we need to keep non-visited nodes along the path.

Pop the stack to retrieve the tuple/pair with the current node and visited status.

• If already being visited, we could append the node's value to the answer.

• If not:

  • First, push the current node but with visited status

  • Second, push the right-child node with non-visited status (if the node exists)

  • Last, push the left-child node with non-visited status (if the node exists)

🤖 Python3

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        # (base case)
        if not root: return []
        if not root.left and not root.right: return [root.val]
        
        # ==================================================
        #  Binary Tree + Post-order Traversal              =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        ans = []
        stack = [(root, False)]
        
        while stack:
            node, visited = stack.pop()
            
            if node:
                if visited:
                    ans.append(node.val)
                else:
                    stack.append((node, True))
                    stack.append((node.right, False))
                    stack.append((node.left, False))
                    
        return ans
    
        '''
        # ==================================================
        #  Binary Tree + Post-order Traversal              =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]
        '''

🤖 Java

class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */
    
    public List<Integer> postorderTraversal(TreeNode root) {
        /* base case */
        if(root == null) return new ArrayList<>();
        
        List<Integer> result = new ArrayList<>();
        Stack<Pair<TreeNode, Boolean>> stack = new Stack<Pair<TreeNode, Boolean>>();
        stack.push(new Pair<TreeNode, Boolean>(root, false));
        
        while(!stack.isEmpty()) {
            Pair<TreeNode, Boolean> object = stack.pop();
            TreeNode node = object.getKey();
            Boolean visited = object.getValue();
            
            if(visited == true) result.add(node.val);
            else {
                stack.push(new Pair<TreeNode, Boolean>(node, true));
                if(node.right != null) stack.push(new Pair<TreeNode, Boolean>(node.right, false));
                if(node.left != null) stack.push(new Pair<TreeNode, Boolean>(node.left, false));
            }
        }
        
        return result;
    }
}