Question

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

Note:

Bonus points if you could solve it both recursively and iteratively.

Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root is None:
            return True
        if root.left is None and root.right is None:
            return True
        elif root.left is not None and root.right is not None:
            return self.isMirror(root.left, root.right)
        else:
            return False

    def isMirror(self, left_root, right_root):
        # val
        if left_root.val != right_root.val:
            return False

        # One side
        if left_root.left is not None and right_root.right is not None:
            valid = self.isMirror(left_root.left, right_root.right)
            if not valid:
                return False
        elif (left_root.left is not None and right_root.right is None) or \
        (left_root.left is None and right_root.right is not None):
            return False

        # The other side
        if left_root.right is not None and right_root.left is not None:
            valid = self.isMirror(left_root.right, right_root.left)
            if not valid:
                return False
        elif (left_root.right is not None and right_root.left is None) or \
        (left_root.right is None and right_root.left is not None):
            return False

        return True