題目描述

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

B 是 A 的子結構， 即 A 中有出現和 B 相同的結構和節點值。

例如: 給定的樹 A:

     3
    / \
   4   5
  / \
 1   2

給定的樹 B：

   4 
  /
 1

返回 true，因為 B 與 A 的一個子樹擁有相同的結構和節點值。

0 <= 節點個數 <= 10000

題目樣例

示例 1

輸入

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

輸出

false

示例 2

輸入

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

輸出

true

題目思考

1. 子結構有哪些性質?

解決方案

思路

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

復雜度

• 時間復雜度          O(MN)
• 假設 A 和 B 的節點數目分別是 M 和 N, 那么最差情況是對于每個 A 節點, 都要調用一次 match 方法遍歷整個 B 樹, 所以時間復雜度是           O(MN)
• 空間復雜度          O(M)
• isSubStructure 遞歸調用則最多使用           O(M) 遞歸棧空間, match 遞歸調用使用           O(min(M, N)) 遞歸棧空間, 所以整體空間復雜度為           O(M)

代碼

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if not A or not B:
            # 根據題意, B如果是空樹一定不滿足條件, 而A是空樹的話B更不可能是其子結構了
            return False

        def match(a, b):
            if not b:
                # 因為A的子樹部分可以有部分節點是B沒有的, 所以如果當前b節點是空的話是滿足條件的情況, 直接返回true
                return True
            if not a:
                # 此時b節點還有值, 但a節點是空了, B不可能是A的子結構
                return False
            # 既要當前a和b的值相等, 同時各自左右子樹部分也要匹配
            return a.val == b.val and match(a.left, b.left) and match(
                a.right, b.right)

        # B是A的子結構的充要條件: 要么當前A和B匹配, 要么A的左右子節點和B匹配
        return match(A, B) or self.isSubStructure(
            A.left, B) or self.isSubStructure(A.right, B)