Invert a Binary Tree

Invert the tree: swap the left and right child of every node, and return the root.

The tests write a tree as a level-order list (row by row, left to right) with None for a missing child: [3, 9, 20, None, None, 15, 7] is a root 3 with children 9 and 20, where 20 has children 15 and 7.

For [4, 2, 7, 1, 3, 6, 9] the answer is [4, 7, 2, 9, 6, 3, 1].

Examples

Example 1

Input:

invert_tree(root)  # root = [4, 2, 7, 1, 3, 6, 9]

Output:

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

Example 2

Input:

invert_tree(root)  # root = [2, 1, 3]

Output:

[2, 3, 1]

Constraints

• 0 <= number of nodes <= 100000
• The tree is not deeper than 800 levels.