Problem Description

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

Example 1:

226.1.jpg

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

Example 2:

226.2.jpg

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

My Idea

My idea here was to use recursion and DFS. If the root has no children return root, else swap the left and the right children and invert them.

My solution

from typing import Optional
# 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

# Time Complexity: O(n)
def invertTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root:
        return None
    if not root.left and not root.right:
        return root
    temp = root.left
    root.left = invertTree(root.right)
    root.right = invertTree(temp)
    return root