Problem
Given the root of a binary tree, check whether it is a mirror of itself (symmetric around its center).
Example
Input: [1,2,2,3,4,4,3]
Output: trueInput: [1,2,2,null,3,null,3]
Output: falseSolution
Recursively compare left and right subtrees. They’re mirrors if values match and (left.left == right.right) and (left.right == right.left).
def is_symmetric(root):
def mirror(a, b):
if not a and not b: return True
if not a or not b: return False
return a.val == b.val and mirror(a.left, b.right) and mirror(a.right, b.left)
return mirror(root.left, root.right) if root else Truefunction isSymmetric(root) {
function mirror(a, b) {
if (!a && !b) return true;
if (!a || !b) return false;
return a.val === b.val && mirror(a.left, b.right) && mirror(a.right, b.left);
}
return root ? mirror(root.left, root.right) : true;
}bool mirror(TreeNode* a, TreeNode* b) {
if (!a && !b) return true;
if (!a || !b) return false;
return a->val == b->val && mirror(a->left, b->right) && mirror(a->right, b->left);
}
bool isSymmetric(TreeNode* root) {
return root ? mirror(root->left, root->right) : true;
}private boolean mirror(TreeNode a, TreeNode b) {
if (a == null && b == null) return true;
if (a == null || b == null) return false;
return a.val == b.val && mirror(a.left, b.right) && mirror(a.right, b.left);
}
public boolean isSymmetric(TreeNode root) {
return root == null || mirror(root.left, root.right);
}Complexity
- Time: O(n)
- Space: O(h) recursion stack
Explanation
Two trees are mirrors when they have the same root value AND the left subtree of one mirrors the right subtree of the other.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?