226. Invert Binary Tree
❤️ 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!
root of a binary tree, invert the tree, and return its root.
Input: root = [4,2,7,1,3,6,9] Output: [4,7,2,9,6,3,1]
Input: root = [2,1,3] Output: [2,3,1]
Input: root =  Output: 
This is a recursive algorithm. There's some tips for ya!
- Always check the base case first (if root is empty)
- 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
selfall 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!