145. Binary Tree Postorder Traversal

Easy LeetCode

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]

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]

Example 3

Input: root = []

Output: []

Example 4

Input: root = [1]

Output: [1]

Constraints

• The number of nodes in the tree is in the range [0, 100]
• -100 <= Node.val <= 100

How to solve the problem

Code

• DFS (Recursion)

# 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]:
        # Postorder: Left-Right-Root
        ans = []
        def dfs(node):
            # Determine base case first(stop rucursion)
            if node is None:
                return
            dfs(node.left) # left
            dfs(node.right) # right
            ans.append(node.val) # postorder
        dfs(root)
        return ans

• Iterations with stack

# 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]:
        # Postorder: Left-Right-Root
        if root is None:
            return []
        stack = [root] # Push root into stack first
        result = [] # Define empty array
        while stack:
            node = stack.pop() # Popout root first
            result.append(node.val) # Put the node which was poped out into result
            # result.append(stack.pop().val)
            if node.left:
                stack.append(node.left) # Push left first, then reverse the whole array
            if node.right:
                stack.append(node.right) # Push right next, put out right first.
        return result[::-1] # Reverse array to get the final answer

Complexity

• Time complexity: O(n), n == number of nodes
• Space complexity: O(n)