Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3]
is symmetric:
1 / \ 2 2 / \ / \ 3 4 4 3
But the following [1,2,2,null,3,null,3]
is not:
1 / \ 2 2 \ \ 3 3
Source
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_symmetric(root):
"""Simplest solution using recursion.
Tree is symetric if left subtree (p) is the mirror of RIGHT subtree (q)
i.e. p.val = q.val
AND p.left = q.right
AND p.right = q.left
Time Complexity: O(n)
Space Complexity: O(n).
"""
def is_mirror(left, right):
if not left or not right:
return left == right
return (left.val == right.val
and is_mirror(left.left, right.right)
and is_mirror(left.right, right.left))
return is_mirror(root, root)
Solve it both recursively and iteratively.
def is_symmetric(root):
"""Iterative approach.
Time Complexity: O(n)
Space Complexity: O(n)
"""
if not root:
return True
stack = [(root.left, root.right)]
while stack:
left, right = stack.pop()
if left is None and right is None:
continue
if left is None or right is None:
return False
if left.val != right.val:
return False
stack.append((left.left, right.right))
stack.append((left.right, right.left))
return True