Leetcode 101: Symmetric Tree

https://leetcode.com/problems/symmetric-tree/

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

 

Code

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

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return not root or self.dfs(root.left, root.right)
        
    def dfs(self, root1, root2):
        if (not root1 and root2) or (not root2 and root1):
            return False
        elif not root1 and not root2:
            return True
        elif root1.val == root2.val:
            return self.dfs(root1.left, root2.right) and self.dfs(root1.right, root2.left)
        else:
            return False

 

Idea

Maintain two pointers pointing to symmetric positions in the tree. If the two tree nodes being pointed to are not None and have same value, then recursively check if their children in the symmetric positions are the same. If the two tree nodes being pointed to are both None, it also indicates they are symmetric.