101. Symmetric Tree
Your function receives the root of a binary tree — each node exposes val, left, and right. Report whether the whole tree is a mirror of itself: fold it along a vertical line through the root, and every node must land exactly on a node with the same value.
Put differently, the left subtree and the right subtree must be reflections of each other — the left child of one corresponds to the right child of the other, all the way down. Return true if the tree is symmetric and false otherwise.
Note that matching values alone are not enough: the shape has to mirror too.
Example 1:
Input: root = [1, 2, 2, 3, 4, 4, 3]
Output: true
Explanation: Folding along the root: the two 2s line up, 3 pairs with 3, and 4 pairs with 4. Every node has a mirror partner, so the tree is symmetric.
Example 2:
Input: root = [1, 2, 2, null, 3, null, 3]
Output: false
Explanation: Both 2s carry their 3 as a right child. A mirror would need one 3 on the left and the other on the right, so the tree is not symmetric.
Constraints:
- 1 ≤ number of nodes ≤ 1000
- -100 ≤ Node.val ≤ 100
Hints:
A tree is symmetric exactly when its left subtree and right subtree are mirrors. Try writing a helper that answers: are these two subtrees mirrors of each other?
Two subtrees mirror each other when both are empty, or when their roots match AND the left child of one mirrors the right child of the other (both cross-pairings). Recurse on those crossed pairs — or push the pairs onto a queue for an iterative version.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, 2, 2, 3, 4, 4, 3]
Expected output: true