Invert Binary Tree

Given the root of a binary tree, invert it: every node's left and right children should be swapped, recursively, throughout the whole tree. Return the root of the inverted tree.

Assume nodes are represented with a simple class:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Example 1

Input (level-order): [4, 2, 7, 1, 3, 6, 9]

Output (level-order): [4, 7, 2, 9, 6, 3, 1]

The tree

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

becomes

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

Example 2

Input: [2, 1, 3] → Output: [2, 3, 1]

Example 3

Input: [] (empty tree) → Output: []

Constraints

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