Introduction

In this blog post, we will explore how to solve the LeetCode problem "145" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given the root of a binary tree, return the postorder traversal of its nodes' values. Example 1: Input: root = [1,null,2,3] Output: [3,2,1] Explanation: Example 2: Input: root = [1,2,3,4,5,null,8,null,null,6,7,9] Output: [4,6,7,5,2,9,8,3,1] Explanation: Example 3: Input: root = [] Output: [] Example 4: Input: root = [1] Output: [1] Constraints: The number of the nodes in the tree is in the range [0, 100]. -100 <= Node.val <= 100 Follow up: Recursive solution is trivial, could you do it iteratively?

Explanation

• The core idea is to simulate the call stack using a stack data structure to perform postorder traversal iteratively. We process a node only after its left and right subtrees are processed.
  • We utilize a last_visited node to track which node was visited last so we know when to go up the tree.
  • If the current node has no left or right child or if the last visited node is the left or right child of current node, the current node is visited. Otherwise, we need to go down to the left child first if possible, and then the right child.

• Time Complexity: O(N), Space Complexity: O(N)

Code

    from typing import List, Optional

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        result = []
        stack = [root]
        last_visited = None

        while stack:
            node = stack[-1]  # Peek at the top of the stack

            # If the node has no children, or both children have been visited
            # OR if last_visited is the immediate child of current node

            if (not node.left and not node.right) or \
               (last_visited and (node.left == last_visited or node.right == last_visited)):
                result.append(node.val)
                last_visited = stack.pop()
            else:
                # Push right child first to stack, followed by left child.
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)

        return result