《劍指offer》面試題14：樹的子結構（Python）-有解無憂

題目描述

輸入兩棵二叉樹A，B，判斷B是不是A的子結構，（ps：我們約定空樹不是任意一個樹的子結構）

題目決議

這個題目很明顯可以使用遞回來做，我們只需要判斷其子數的結構是不是相同的就行了，這里也撰寫了兩個函式，代碼如下：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
　　　　  #空樹不是任何一個樹的子結構，不符合定義，直接回傳Fasle
        if pRoot1 == None or pRoot2 == None:
            return False
        return self.isSubtree(pRoot1, pRoot2)

    def isSubtree(self, p1, p2):
        if p2 == None:
            return True
        if p1 == None:
            return p1 == p2
        res = False
        if p1.val == p2.val:#假設我們輸入進來的兩棵樹是相同的，則來判斷是否是相同的，如果是相同的則輸出True,相同的樹互為子結構
            res = self.isSubtree(p1.left, p2.left) and self.isSubtree(p1.right, p2.right)
　　　　#如果輸入進來的兩顆樹是不相同的，那么大樹的左子樹和右子樹其中有一個為p2樹所在的樹則回傳為真
        return res or self.isSubtree(p1.left, p2) or self.isSubtree(p1.right, p2)

解法二：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        #空樹不是任意樹的子結構，因此回傳False
        if A == None or B == None:
            return False
        #兩棵樹是完全相同的，則互為子結構
        return self.dfs(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)
    
    #利用dfs()函式來判斷兩棵樹是否是相同
    def dfs(self, A: TreeNode, B: TreeNode) -> bool:
        #為啥B樹都啥也沒了，還能夠和A一樣？回傳True？
        if B == None:
            return True
        if A == None:
            return False
        return A.val == B.val and self.dfs(A.left,B.left) and self.dfs(A.right,B.right)

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/145117.html

標籤：其他

上一篇：Monotonic stack to solve leetcode 84: Largest Rectangle in Histogram

下一篇：Fast and slow pointers for cycle detection in linked list