EasyLeetCode #226Trees

Invert Binary Tree

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

Constraints

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

Examples

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

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

Solution

Approach

Recursively swap left and right children for each node. Can also be done iteratively with BFS/DFS.

def invertTree(root):
    if not root:
        return None
    root.left, root.right = root.right, root.left
    invertTree(root.left)
    invertTree(root.right)
    return root

Complexity

Time:O(n)

Space:O(h)

Hints

1.Think recursively
2.Swap children at each node
3.Base case: null node

Asked at

Google