Symmetric Binary Tree

Bronze

10000ms500MB

You are given the root of a binary tree, root. Return whether it is symmetric.

A tree is symmetric if it looks the same as its own mirror image around the root: the left subtree is a mirror of the right subtree, matching both shape and node values.

Tree Encoding

Your function receives root as a TreeNode. The node type is provided for you, with val, left, and right fields.

The examples below write the tree as its level-order traversal, where null marks a missing child of a listed node and trailing nulls are omitted. That is only how the tree is displayed; the decoding is done for you.

Constraints

The number of nodes in root is in the range $[1, 10^5]$ .
$-10^9 \leq$ Node.val $\leq 10^9$

Examples

Example 1

Input

root = [1, 2, 2, 3, 4, 4, 3]

root

Output

true

Explanation

The left subtree `[2,3,4]` mirrors the right subtree `[2,4,3]`: both roots are `2`, and `3` on the far left matches `3` on the far right while `4` matches `4` in the middle.

Example 2

Input

root = [1, 2, 2, null, 3, null, 3]

root

Output

false

Explanation

Both subtrees have the same values, `2` with a child `3`, but the `3` hangs off the same side (the right) under each `2` instead of mirrored sides, so the shapes do not actually mirror each other.

Example 3

Input

root = [1]

root

Output

true

Explanation

A single node has no children to compare, so it is trivially symmetric.

Loading editor...

Run checks the sample cases; Submit runs every case.

Samples 3

Custom 0

passedwrong answertime limiterrorran, no expected valuenot run

sample

root =tree

Expected

true

Symmetric Binary Tree

Bronze

10000ms500MB

You are given the root of a binary tree, root. Return whether it is symmetric.

A tree is symmetric if it looks the same as its own mirror image around the root: the left subtree is a mirror of the right subtree, matching both shape and node values.

Tree Encoding

Your function receives root as a TreeNode. The node type is provided for you, with val, left, and right fields.

Constraints

The number of nodes in root is in the range $[1, 10^5]$ .
$-10^9 \leq$ Node.val $\leq 10^9$

Examples

Example 1

Input

root = [1, 2, 2, 3, 4, 4, 3]

root

Output

true

Explanation

The left subtree `[2,3,4]` mirrors the right subtree `[2,4,3]`: both roots are `2`, and `3` on the far left matches `3` on the far right while `4` matches `4` in the middle.

Example 2

Input

root = [1, 2, 2, null, 3, null, 3]

root

Output

false

Explanation

Both subtrees have the same values, `2` with a child `3`, but the `3` hangs off the same side (the right) under each `2` instead of mirrored sides, so the shapes do not actually mirror each other.

Example 3

Input

root = [1]

root

Output

true

Explanation

A single node has no children to compare, so it is trivially symmetric.

Loading editor...

Run checks the sample cases; Submit runs every case.

Samples 3

Custom 0

passedwrong answertime limiterrorran, no expected valuenot run

sample

root =tree

Expected

true