題目描述

輸入兩棵二叉樹(shù) A 和 B，判斷 B 是不是 A 的子結(jié)構(gòu)。(約定空樹(shù)不是任意一個(gè)樹(shù)的子結(jié)構(gòu))

B 是 A 的子結(jié)構(gòu)， 即 A 中有出現(xiàn)和 B 相同的結(jié)構(gòu)和節(jié)點(diǎn)值。

例如: 給定的樹(shù) A:

     3
    / \
   4   5
  / \
 1   2

給定的樹(shù) B：

   4 
  /
 1

返回 true，因?yàn)?B 與 A 的一個(gè)子樹(shù)擁有相同的結(jié)構(gòu)和節(jié)點(diǎn)值。

0 <= 節(jié)點(diǎn)個(gè)數(shù) <= 10000

題目樣例

示例 1

輸入

A = [1,2,3], B = [3,1]

輸出

false

示例 2

輸入

A = [3,4,5,1,2], B = [4,1]

輸出

true

題目思考

1. 子結(jié)構(gòu)有哪些性質(zhì)?

解決方案

思路

• 分析題目, B 是 A 的子結(jié)構(gòu)的話(huà), 那么 B 的節(jié)點(diǎn)結(jié)構(gòu)需要完全是 A 的某一部分, 而且該部分中的一部分子樹(shù)可以不在 B 中(例如題目中 A 的 2 號(hào)節(jié)點(diǎn)就不在 B 中)
• 所以我們可以額外定義一個(gè)方法, 來(lái)遞歸比較當(dāng)前 A 和 B 節(jié)點(diǎn)是否滿(mǎn)足子結(jié)構(gòu)關(guān)系
• 然后從 A 和 B 的根節(jié)點(diǎn)開(kāi)始調(diào)用該方法, 如果當(dāng)前滿(mǎn)足條件就直接返回 true, 否則就將 A 移動(dòng)到其左右子節(jié)點(diǎn)位置, 重新與 B 的根節(jié)點(diǎn)比較即可
• 下面代碼中有詳細(xì)的注釋, 方便大家理解

復(fù)雜度

• 時(shí)間復(fù)雜度          O(MN)
• 假設(shè) A 和 B 的節(jié)點(diǎn)數(shù)目分別是 M 和 N, 那么最差情況是對(duì)于每個(gè) A 節(jié)點(diǎn), 都要調(diào)用一次 match 方法遍歷整個(gè) B 樹(shù), 所以時(shí)間復(fù)雜度是           O(MN)
• 空間復(fù)雜度          O(M)
• isSubStructure 遞歸調(diào)用則最多使用           O(M) 遞歸棧空間, match 遞歸調(diào)用使用           O(min(M, N)) 遞歸?？臻g, 所以整體空間復(fù)雜度為           O(M)

代碼

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if not A or not B:
            # 根據(jù)題意, B如果是空樹(shù)一定不滿(mǎn)足條件, 而A是空樹(shù)的話(huà)B更不可能是其子結(jié)構(gòu)了
            return False

        def match(a, b):
            if not b:
                # 因?yàn)锳的子樹(shù)部分可以有部分節(jié)點(diǎn)是B沒(méi)有的, 所以如果當(dāng)前b節(jié)點(diǎn)是空的話(huà)是滿(mǎn)足條件的情況, 直接返回true
                return True
            if not a:
                # 此時(shí)b節(jié)點(diǎn)還有值, 但a節(jié)點(diǎn)是空了, B不可能是A的子結(jié)構(gòu)
                return False
            # 既要當(dāng)前a和b的值相等, 同時(shí)各自左右子樹(shù)部分也要匹配
            return a.val == b.val and match(a.left, b.left) and match(
                a.right, b.right)

        # B是A的子結(jié)構(gòu)的充要條件: 要么當(dāng)前A和B匹配, 要么A的左右子節(jié)點(diǎn)和B匹配
        return match(A, B) or self.isSubStructure(
            A.left, B) or self.isSubStructure(A.right, B)