題目:

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

給定兩個二元樹,判斷它們是否一模一樣

上一題都用dfs的想法去做,所以這題我採用bfs的迴圈做法

# 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: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        r1=[p]
        r2=[q]
        while r1!=[] and r2!=[]:
            if r1[0]==None and r2[0]==None:
                r1.pop(0)
                r2.pop(0)
                continue
            
            if r1[0]!=None and r2[0]==None:
                return False
            
            if r1[0]==None and r2[0]!=None:
                return False
                
            if r1[0].val==r2[0].val:
                r1.append(r1[0].left)
                r2.append(r2[0].left)
                r1.append(r1[0].right)
                r2.append(r2[0].right)
                r1.pop(0)
                r2.pop(0)
            else:
                return False
        return True

簡單來說就是一層一層全部抓出來比
有兩個陣列分別儲存兩個樹待確認的節點
由於先進先確認,儲存陣列用類似queue的方式去實作
檢測部分先檢測含有None的幾種可能
都沒None的話就確認值是否一樣
確認完就提出,同時將它們的left跟right放入各自的儲存陣列
完全通過的話就回傳True
最後執行時間32ms(faster than 89.99%)

另外這裡順便介紹在討論區出現的簡短dfs遞迴解

# 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: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p and q:
            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        return p is q

先確認兩樹的對應節點是否含有None
有的話則判斷異同回傳
無的話就判斷異同同時向下探索
最後執行時間32ms(faster than 89.91%)

那我們下題見