Breadth first search

Tree - Breadth_first_search.py

#Breadth first search
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        from collections import deque
        #Judge whether two binary trees are empty
        if not p and not q:
            return True
        elif not p or not q:
            return False
        #If they are not empty, the queue is used to store the nodes of the binary tree
        #Join the two root nodes first
        queue_p = deque([p])
        queue_q = deque([q])

        while queue_p and queue_q:
            node_p = queue_p.popleft()
            node_q = queue_q.popleft()
            
            #Comparison value
            if node_p.val != node_q.val:
                return False
            #Comparative structure
            left_p, right_p = node_p.left, node_p.right
            left_q, right_q = node_q.left, node_q.right
            #Here, XOR is used to directly judge whether two are empty and one of them is null
            #Return 0 if ^ same, otherwise return 1
            #The statement will be executed only if 1 is returned, that is, false is returned
            if (not left_p) ^ (not left_q):
                return False
            if (not right_p) ^ (not right_q):
                return False
            #When the value is the same as the structure, the child nodes are queued from left to right when the child node is not empty
            if left_p:
                queue_p.append(left_p)
            if right_p:
                queue_p.append(right_p)
            if left_q:
                queue_q.append(left_q)
            if right_q:
                queue_q.append(right_q)
        
        #Finally, we need to judge whether the queue is empty
        #If the queues are not all empty, the binary tree structure is different
        return not queue_p and not queue_q