Python iterative way using a queue


  • 7
    S

    Each iteration, it checks whether two nodes are symmetric and then push (node1.left, node2.right), (node1.right, node2.left) to the end of queue.

    class Solution:
    # @param root, a tree node
    # @return a boolean
    def isSymmetric(self, root):
        if not root:
            return True
    
        dq = collections.deque([(root.left,root.right),])
        while dq:
            node1, node2 = dq.popleft()
            if not node1 and not node2:
                continue
            if not node1 or not node2:
                return False
            if node1.val != node2.val:
                return False
            # node1.left and node2.right are symmetric nodes in structure
            # node1.right and node2.left are symmetric nodes in structure
            dq.append((node1.left,node2.right))
            dq.append((node1.right,node2.left))
        return True

  • 1
    C

    It seems that you don't need use deque in this case, Python queue (list) can accomplish this as well:

    def isSymmetric(self, root):
        if not root:
            return True
        queue = []
        queue.append((root.left, root.right))
        while queue:
            l, r = queue.pop(0)
            if not l and not r:
                continue
            if not l or not r:
                return False
            if l.val != r.val:
                return False
            queue.append((l.left, r.right))
            queue.append((l.right, r.left))
        return True

  • 0
    A

    Nice structure. Simplify a little more without using too many "not".

    class Solution(object):
        def isSymmetric(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            if not root: return True
            q = deque([(root.left, root.right)])
            while q:
                l, r = q.popleft()
                if l and r and l.val == r.val:
                    q.extend([(l.right, r.left), (l.left, r.right)])
                elif l == r:
                    continue
                else:
                    return False
            return True
    

  • 0
    A

    @caikehe said in Python iterative way using a queue:

    It seems that you don't need use deque in this case, Python queue (list) can accomplish this as well:

    def isSymmetric(self, root):
        if not root:
            return True
        queue = []
        queue.append((root.left, root.right))
        while queue:
            l, r = queue.pop(0)
            if not l and not r: #If this condition is true. Will it return true?
                continue #What will this do? 
            if not l or not r: 
                return False
            if l.val != r.val:
                return False
            queue.append((l.left, r.right)) #When does this execute?
            queue.append((l.right, r.left)) #And this? 
        return True #This executes if first condition is true? 
    

    Can you please explain the flow of this code? I will really appreciate it. I am new and I really want to understand rather than cram any of it. Thank you!


Log in to reply
 

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