LC 226 - Invert Binary Tree

Question

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: []

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Links

Question here and solution here

Solution

concept

Use DFS and recursion to swap left and right, and then move to the child node. Note that once we swap the node in code, it actually make the current node point to the new (swapped) node, i.e. the child node and grandchild node also gets swapped.

code

# 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 node
        # root.left, root.right = root.right, root.left
        tmp = root.left
        root.left = root.right
        root.right = tmp

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

        return root

Complexity

time: $O(n)$ where $n$ is the number of node in the tree
space: $O(n)$