Create a helper that checks if two trees are mirrors:
def isSymmetric(root):
if root == null:
return true
return isMirror(root.left, root.right)
def isMirror(t1, t2):
if t1 == null and t2 == null:
return true
if t1 == null or t2 == null:
return false
return (t1.val == t2.val and
isMirror(t1.left, t2.right) and
isMirror(t1.right, t2.left))
The insight: in a mirror, 's left corresponds to 's right, and 's right corresponds to 's left.
Time: . Space: .