Binary Tree Postorder Traversal

lcpy gen -n 145   # by problem number
lcpy gen -s binary_tree_postorder_traversal   # by problem name

Input: root = [1,null,2,3]
Output: [3,2,1]

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,6,7,5,2,9,8,3,1]

Input: root = []
Output: []

Input: root = [1]
Output: [1]

from leetcode_py import TreeNode


class Solution:
    # Time: O(n)
    # Space: O(h) where h is the height of the tree
    def postorder_traversal(self, root: TreeNode[int] | None) -> list[int]:
        if not root:
            return []

        result: list[int] = []
        stack: list[TreeNode[int]] = [root]

        while stack:
            node = stack.pop()
            result.append(node.val)

            # Push left first, then right (so right is processed first)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)

        # Reverse to get postorder (left, right, root)
        return result[::-1]