Mirror Tree

Binary TreeDepth-First SearchRecursionTree

Given the root node of a binary tree, transform the tree into its mirror image and return the new root. The mirror of a tree is obtained by swapping the left and right children of all nodes at each level.

Example 1

Input

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

Output

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

Explanation. The original tree is: 4 / \ 2 7 / \ / \ 1 3 6 9 After mirroring, the modified tree is: 4 / \ 7 2 / \ / \ 9 6 3 1

Example 2

Input

[
  1,
  2
]

Output

[1, null, 2]

Explanation. The original tree is: 1 / 2 After mirroring, the modified tree is: 1 \ 2

Example 3

Input

[]

Output

[]

Explanation. An empty tree returns an empty array.

Follow-up: Can you solve this problem recursively and iteratively?

Constraints:

The tree will have at most 1000 nodes. Each node's value will be a non-negative integer.

Views: 3