binary-tree-postorder-traversal.py

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

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

Input: root = []
Output: []
"""
# 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

from typing import Optional, List
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # postorder means Left -> right -> root

        if not root:
            return []

        def traverse(node: TreeNode):
            if not node:
                return []

            return traverse(node.left) + traverse(node.right) + [node.val]
        
        return traverse(root)