Easy Recursive Max Advanced Trees
In plain English: Check whether the left and right halves of a binary tree are mirror images of each other.
Two subtrees are mirrors if their roots match and each tree's left subtree mirrors the other's right subtree — recurse with crossed pairs.
Prompt
Check if a binary tree is symmetric (a mirror image of itself).
Try to write it from scratch before scrolling down.
Solution
def is_symmetric(root):
def is_mirror(t1, t2):
if not t1 and not t2:
return True
if not t1 or not t2:
return False
return (t1.val == t2.val and
is_mirror(t1.left, t2.right) and # cross-compare
is_mirror(t1.right, t2.left))
return is_mirror(root, root) if root else True
# Test: tree [1,2,2,3,4,4,3] => True
# Test: tree [1,2,2,null,3,null,3] => False