LeetCode如何判斷樹的子結(jié)構(gòu)

題目描述

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

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

例如: 給定的樹 A:

     3
    / \
   4   5
  / \
 1   2

給定的樹 B：

   4 
  /
 1

返回 true，因為 B 與 A 的一個子樹擁有相同的結(jié)構(gòu)和節(jié)點值。

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

復(fù)雜度

• 時間復(fù)雜度          O(MN)
• 假設(shè) A 和 B 的節(jié)點數(shù)目分別是 M 和 N, 那么最差情況是對于每個 A 節(jié)點, 都要調(diào)用一次 match 方法遍歷整個 B 樹, 所以時間復(fù)雜度是           O(MN)
• 空間復(fù)雜度          O(M)
• isSubStructure 遞歸調(diào)用則最多使用           O(M) 遞歸?？臻g, 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如果是空樹一定不滿足條件, 而A是空樹的話B更不可能是其子結(jié)構(gòu)了
            return False

        def match(a, b):
            if not b:
                # 因為A的子樹部分可以有部分節(jié)點是B沒有的, 所以如果當(dāng)前b節(jié)點是空的話是滿足條件的情況, 直接返回true
                return True
            if not a:
                # 此時b節(jié)點還有值, 但a節(jié)點是空了, B不可能是A的子結(jié)構(gòu)
                return False
            # 既要當(dāng)前a和b的值相等, 同時各自左右子樹部分也要匹配
            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é)點和B匹配
        return match(A, B) or self.isSubStructure(
            A.left, B) or self.isSubStructure(A.right, B)