All problems

Symmetric Tree

Easy · tree dfs

You are given the root of a binary tree. A tree is symmetric if its left half is a mirror image of its right half, as if the tree were folded down the middle through the root.

In other words, the left subtree of the root and the right subtree of the root must have mirrored shapes, and nodes in mirrored positions must hold equal values. Return true if the tree is symmetric, otherwise false. An empty tree and a tree with only a root are symmetric.

Examples

Example 1

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

Output: true

Both sides hold 2, and under them the outer children are 3 and 3 and the inner children are 4 and 4.

Example 2

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

Output: false

Each side has a single child, but both children sit on the right, so the shapes are not mirrored.

Example 3

Input: root = [1, 2, 2, 3, 4, 4, 5]

Output: false

The shapes match, but the outer leaves hold 3 and 5, so the values differ.

Constraints