226. Invert Binary Tree

Problem

Invert a binary tree.

4 / \ 2 7 / \ / \ 1 3 6 9

Output:

4 / \ 7 2 / \ / \ 9 6 3 1

Thought Process

    Can solve this question recursively.
  • if the root is None, return None
  • else, revert root's left tree recursively, revert root's right tree recursively
  • swap left, right tree

White Board

Below is the white board:

Code

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return None

        self.invertTree(root.left)
        self.invertTree(root.right)
        self.left, self.right = self.right, self.left

        return root

Complexity

  • Time complexity is O(n)

Optimization

Maybe have an iterative solution...