Iterative and Recursive solutions in Python with explanations


  • 0
    R

    Iterative solution:
    BFS, each layer should be palindromic, otherwise not symmetric.

    class Solution(object):
        def isSymmetric(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            st = [root]
            while not all([x==None for x in st]):
                children = []
                for n in st:
                    children.extend([n.left, n.right])
                childrenVal = [(x.val if x else None) for x in children ]
                if childrenVal != childrenVal[::-1]:
                    return False
                st = [x for x in children if x]
            return True
    

    Recursive solution:
    treeA is symmetric only if treeA.left.val == treeA.right.val and treeA.left and treeA.right are both symmetric

    class Solution(object):
        def isSymmetric(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            if root == None:
                return True
            return self.treeEqual(root.left, root.right)
            
        def treeEqual(self, n1, n2):
            if n1 == None == n2:
                return True
            if (n1 == None and n2 != None) or (n1 != None and n2 == None):
                return False
            return (n1.val == n2.val) and self.treeEqual(n1.left, n2.right) and self.treeEqual(n1.right, n2.left)
    

Log in to reply
 

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