LeetCode 101 - Symmetric Tree Problem

Problem Statement

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

 

Follow up: Solve it both recursively and iteratively.

Solution:

from collections import deque # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None #Recursive approach class Solution: def isSymmetric(self, root: TreeNode) -> bool: if not root: return True return self.check(root.left, root.right) def check(self, left, right): if not left and not right: return True if not left or not right: return False if left.val == right.val: valid1 = self.check(left.left, right.right) valid2 = self.check(left.right, right.left) return valid1 and valid2 return False #Iterative apporach class Solution: def isSymmetric(self, root: TreeNode) -> bool: if not root: return True q = deque() q.append(root) q.append(root) while len(q)>0: n1 = q.popleft() n2 = q.popleft() if not n1 and not n2: continue if not n1 or not n2: return False if n1.val!=n2.val: return False q.append(n1.left) q.append(n2.right) q.append(n1.right) q.append(n2.left) return True