100. 相同的樹

題目來源：力扣（LeetCode）https://leetcode-cn.com/problems/same-tree

題目

給定兩個(gè)二叉樹，編寫一個(gè)函數(shù)來檢驗(yàn)它們是否相同。

如果兩個(gè)樹在結(jié)構(gòu)上相同，并且節(jié)點(diǎn)具有相同的值，則認(rèn)為它們是相同的。

示例 1:

輸入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

輸出: true

示例 2:

輸入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

輸出: false

示例 3:

輸入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

輸出: false

解題思路

由題意可知，若兩個(gè)二叉樹相同，那么兩個(gè)樹在結(jié)構(gòu)上相同，并且節(jié)點(diǎn)具有相同的值。那么，我們可以通過深度優(yōu)先搜索（DFS）、廣度優(yōu)先搜索（BFS）去判斷兩個(gè)二叉樹是否相同。

思路：DFS、BFS

深度優(yōu)先搜索（DFS）

使用深度優(yōu)先搜索，遇到的情況及分析如下：

• 當(dāng)兩個(gè)二叉樹都空時(shí)，那么可以判定兩個(gè)二叉樹相同，返回 True；
• 當(dāng)兩個(gè)二叉樹其中一個(gè)為空，而另外一個(gè)不為空時(shí)，那么兩個(gè)二叉樹一定不同的，返回 False；
• 當(dāng)兩個(gè)二叉樹都不為空的情況下，要對節(jié)點(diǎn)的值進(jìn)行判斷。分別對兩個(gè)二叉樹的根節(jié)點(diǎn)，以及根節(jié)點(diǎn)的左右子樹的值進(jìn)行判斷。若出現(xiàn)不同，則表示兩個(gè)二叉樹不同，返回 False，否則返回 True。

具體的代碼見【代碼實(shí)現(xiàn) # 深度優(yōu)先搜索】

廣度優(yōu)先搜索（BFS）

同樣的，我們也可以使用廣度優(yōu)先搜索的方法來解決這個(gè)問題，這里我們要借助輔助隊(duì)列，算法具體的過程如下：

• 判斷兩個(gè)二叉樹是否同時(shí)為空，若是，返回 True；
• 判斷兩個(gè)二叉樹是否其中一個(gè)為空，另一個(gè)不為空，若是，返回 False；
• 當(dāng)兩個(gè)二叉樹都不為空時(shí)，開始廣度優(yōu)先搜索，這里使用隊(duì)列，分別存儲兩個(gè)二叉樹的節(jié)點(diǎn)：
  • 初始先將兩個(gè)二叉樹的根節(jié)點(diǎn)分別放入隊(duì)列中；
  • 出隊(duì)，對出隊(duì)的兩個(gè)節(jié)點(diǎn)的值進(jìn)行比較：
    • 當(dāng)兩個(gè)節(jié)點(diǎn)值不同，那么二叉樹一定不同；
    • 當(dāng)兩個(gè)節(jié)點(diǎn)值相同，繼續(xù)判斷二叉樹的結(jié)構(gòu)是否相同，也就是當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)是否存在為空的情況。同時(shí)為空，判定為相同，但當(dāng)兩個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)僅有一個(gè)為空，那么二叉樹不同。
    • 當(dāng)兩個(gè)節(jié)點(diǎn)值相同，結(jié)構(gòu)也相同時(shí)，將兩個(gè)節(jié)點(diǎn)的非空子節(jié)點(diǎn)分別存入隊(duì)列中。這里需要注意的是，存儲時(shí)，如果子節(jié)點(diǎn)不為空，那么考慮的順序都為從左到右。

當(dāng)前面的算法執(zhí)行結(jié)束后，如果隊(duì)列都為空，那么表示兩個(gè)二叉樹是相同的；如果隊(duì)列不都為空，那么表明二叉樹的結(jié)構(gòu)不同，也就是說兩個(gè)二叉樹不同。

具體的代碼見【代碼實(shí)現(xiàn) # 廣度優(yōu)先搜索】

代碼實(shí)現(xiàn)

# 深度優(yōu)先搜索
# 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:
        
        def dfs(p, q):
            # 兩個(gè)二叉樹都為空的情況
            if p == None and q == None:
                return True
            # 兩個(gè)二叉樹只有一個(gè)為空的情況
            elif p == None or q == None:
                return False
            # 二叉樹都不為空的情況，比較值
            elif p.val == q.val:
                # 當(dāng)根節(jié)點(diǎn)的值相同時(shí)，往下繼續(xù)判斷左右子樹的值
                return dfs(p.left, q.left) and dfs(p.right, q.right)
            # 值不同，返回 False
            return False
            

        return dfs(p, q)

# 廣度優(yōu)先搜索
# 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
        # 判斷兩個(gè)二叉樹是否為空的情況
        if not p and not q:
            return True
        elif not p or not q:
            return False
        # 都不為空的情況，使用隊(duì)列，存儲二叉樹的節(jié)點(diǎn)
        # 先將兩個(gè)根節(jié)點(diǎn)入隊(duì)
        queue_p = deque([p])
        queue_q = deque([q])

        while queue_p and queue_q:
            node_p = queue_p.popleft()
            node_q = queue_q.popleft()
            
            # 比較值
            if node_p.val != node_q.val:
                return False
            # 比較結(jié)構(gòu)
            left_p, right_p = node_p.left, node_p.right
            left_q, right_q = node_q.left, node_q.right
            # 這里使用異或，直接判斷兩個(gè)為空以及其中一個(gè)為空的情況
            # ^ 相同返回 0，否則返回 1
            # 只有返回 1 的情況才會執(zhí)行語句，也就是不同返回 False
            if (not left_p) ^ (not left_q):
                return False
            if (not right_p) ^ (not right_q):
                return False
            # 值與結(jié)構(gòu)相同時(shí)，當(dāng)子節(jié)點(diǎn)非空，將子節(jié)點(diǎn)按照從左到右的順序入隊(duì)
            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)
        
        # 最后需要判斷隊(duì)列是否為空
        # 如果隊(duì)列不都為空，那么表明二叉樹結(jié)構(gòu)不同
        return not queue_p and not queue_q

實(shí)現(xiàn)結(jié)果

實(shí)現(xiàn)結(jié)果 | 深度優(yōu)先搜索

實(shí)現(xiàn)結(jié)果 | 廣度優(yōu)先搜索

歡迎關(guān)注

公眾號 【書所集錄】