❤️ This is one of my favourite leetcode problems. I was in a 1v1 race against someone and I came up with the solution without knowing how to do it, I felt so estatic when my code worked first time!

Problem

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

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

Example 2:

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

Example 3:

Input: root = [] Output: []

Solution

This is a recursive algorithm. There's some tips for ya!

1. Always check the base case first (if root is empty)
2. It is often easier to use a sub-function to do the recursion than it is to use the orignal function, this is because of arguments / dealing with self all the time.

For this problem we can just use the original function :)

# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        
        # Swap the children
        root.left, root.right = root.right, root.left

        # Depth-first-search, we go all the way down the left
        # before inverting the right subtree
        self.invertTree(root.left)
        self.invertTree(root.right)
    
        return root

It is worth memorising this solution, a lot of similar problems use the same format!