Symmetric Tree — Mirror Recursion
Advertisement
Problem 349 · Symmetric Tree
Difficulty: Easy · Pattern: Mirror DFS
Solutions
# Python
def isSymmetric(root):
def mirror(left, right):
if not left and not right: return True
if not left or not right: return False
return (left.val == right.val and
mirror(left.left, right.right) and
mirror(left.right, right.left))
return mirror(root.left, root.right) if root else True
// Java
public boolean isSymmetric(TreeNode root) {
return root == null || mirror(root.left, root.right);
}
boolean mirror(TreeNode l, TreeNode r) {
if (l==null&&r==null) return true;
if (l==null||r==null) return false;
return l.val==r.val && mirror(l.left,r.right) && mirror(l.right,r.left);
}
// C++
bool mirror(TreeNode* l, TreeNode* r) {
if (!l && !r) return true;
if (!l || !r) return false;
return l->val==r->val && mirror(l->left,r->right) && mirror(l->right,r->left);
}
bool isSymmetric(TreeNode* root) { return !root || mirror(root->left, root->right); }
Complexity
- Time: O(n)
- Space: O(h)
Advertisement