Mirror Tree Check

Binary TreeBreadth-First SearchDepth-First SearchTree

Given the root of a binary tree, determine if it is a mirror of itself (i.e., symmetric around its center).

Example 1

Input

Output

true

Explanation. The tree is symmetric around its center.

Example 2

Input

[
  [
    1,
    2,
    2,
    null,
    3,
    null,
    3
  ]
]

Output

false

Explanation. The tree is not symmetric.

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

Constraints:

The number of nodes in the tree is in the range `[1, 1000]`. Each node's value is an integer in the range `[-1000, 1000]`.