458. Self-Mirrored Tree
A glassblower makes decorative ornaments shaped like binary trees, with the design given by root. An ornament is considered balanced in style if folding it along a vertical line through the root makes the left half land exactly on top of the right half.
Return true if the tree is a mirror image of itself: the left subtree of the root must be the reflection of the right subtree, with matching values at reflected positions and matching missing children. Return false otherwise. An empty tree and a single node both count as self-mirrored.
Example 1
- Input:
- root = [5,2,2,1,6,6,1]
- Output:
- true
- Explanation:
The left subtree 2(1,6) reflects to 2(6,1), which equals the right subtree.
Example 2
- Input:
- root = [5,2,2,null,7,null,7]
- Output:
- false
- Explanation:
Both 2-nodes have their 7 on the right side, but a reflection would put it on the left of one of them, so the tree is not symmetric.
Constraints
0 ≤ number of nodes ≤ 105
-1000 ≤ node value ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)