Leetcode 145. Binary Tree Postorder Traversal

Problem

Leetcode 145 - Binary Tree Postorder Traversal

Example:

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]

Approach

When we run the DFS, we can first append the root’s value into the list that we’re planning to go left, and right then append the value to res

Here is the Python code for the solution:

class Solution:
    # recurisve solution
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []

        def postOrder(root):
            if not root:
                return
            
            postOrder(root.left)
            postOrder(root.right)
            res.append(root.val)
        
        return res
        
    # iterative solution
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stack = []
        res = []
        curr = root

        while curr or stack:
            if curr:
                res.append(curr.val)
                stack.append(curr)
                curr = curr.right
            else:
                curr = stack.pop()
                curr = curr.left
        
        res.reverse()
        return res

Time Complexity and Space Complexity

Recursion Method:

Time Complexity: $O(n)$

Space Complexity: $O(n)$

Iterative Method:

Time Complexity: $O(n)$

Space Complexity: $O(n)$