Python Recursive and Non-Recursive Solutions


  • 0

    Recursive (DFS)

    class Solution(object):
        def isSymmetric(self, root):
            return root is None or self.helper(root.left, root.right)
        
        def helper(self, root1, root2):
            if root1 is None or root2 is None:
                return root1 == root2
            if root1.val != root2.val:
                return False
            return self.helper(root1.right, root2.left) and self.helper(root1.left, root2.right)
    

    Non-recursive (BFS)

    from collections import deque
    
    class Solution(object):
        def isSymmetric(self, root):
            if root is None:
                return True
            q = deque([root])
            while q:
                size = len(q)
                nums = []
                for i in range(size):
                    node = q.popleft()
                    if node.left != None:
                        q.append(node.left)
                        nums.append(node.left.val)
                    else:
                        nums.append(None)
                    if node.right != None:
                        q.append(node.right)
                        nums.append(node.right.val)
                    else:
                        nums.append(None)
                if nums != list(reversed(nums)):
                    return False
            return True
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.