Given the root of a binary tree, return true if the tree is a mirror image of itself around its center, meaning the left subtree is the reflection of the right subtree.
Example 1
Input: root = [1,2,2,3,4,4,3]
Output: true
Example 2
Input: root = [1,2,2,null,3,null,3]
Output: false
Both 3s are right children, so the two sides are not reflections.
Constraints
- The number of nodes is in the range 1 to 1000
- -100 <= Node.val <= 100
Hints
Frequently asked at: Microsoft, Amazon, LinkedIn, Bloomberg
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
One slow idea is to build an inverted copy of the tree and compare it with the original, which costs extra memory. Instead, compare the tree with itself in mirrored directions: walk the left subtree and the right subtree together, always pairing an outer node with an outer node and an inner node with an inner node. It is the Same Tree check, except the children are crossed.
Algorithm
- Define
mirror(a, b). If both are null, returntrue; if one is null, returnfalse. - Return
a.val == b.val and mirror(a.left, b.right) and mirror(a.right, b.left). - The answer is
mirror(root.left, root.right).
Time:
O(n)Space: O(h) recursion depthInterview tip: Interviewers often ask for the iterative version: put pairs
(a, b) in a queue, and for each pair push (a.left, b.right) and (a.right, b.left).class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: def mirror(a, b): if a is None and b is None: return True if a is None or b is None or a.val != b.val: return False # outer pair and inner pair must both match return mirror(a.left, b.right) and mirror(a.right, b.left)Β return root is None or mirror(root.left, root.right)Ctrl + Enter runs the examples