Invert Binary Tree

Invert Binary Tree

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

Inverting a binary tree means swapping the left and right children of every node in the tree.

Examples

Example 1:

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

        4                4
       / \    =>        / \
      2   7            7   2
     / \ / \          / \ / \
    1  3 6  9        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

Expected Complexity

• Time: O(n)
• Space: O(h) where h is the height of the tree