Problem URL: Binary tree postorder traversal

We will traverse the tree with recursive DFS, as it is postorder traversal, we first traverse the left subtree, the the right subtree and then append the root to our result.

# 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]:
        res = []

        def traverse(root, res):
            if not root:
                return

            traverse(root.left, res)
            traverse(root.right, res)
            res.append(root.val)

        traverse(root, res)
        return res

Time Complexity: O(n)
Space Complexity: O(n)