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

💡 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