輸入兩棵二叉樹(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)值。

示例

• 輸入：A = [3,4,5,1,2], B = [4,1]

• 輸出：true

限制

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

方法：遞歸

思路：

• 遍歷樹(shù)A 中的節(jié)點(diǎn)與 樹(shù)B 值一致的節(jié)點(diǎn)；

• 根據(jù)步驟一獲取到的的節(jié)點(diǎn)遞歸遍歷是否與 樹(shù)B 的樹(shù)結(jié)構(gòu)是否一致。

流程：

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度： O(MN)，其中 M,N 分別為樹(shù) A 和 樹(shù) B 的節(jié)點(diǎn)數(shù)量；先序遍歷樹(shù) A 占用 O(M) ，每次調(diào)用 recur(A, B) 判斷占用 O(N) 。

• 空間復(fù)雜度： O(M)，當(dāng)樹(shù) A 和樹(shù) B 都退化為鏈表時(shí)，遞歸調(diào)用深度最大。當(dāng) M≤N 時(shí)，遍歷樹(shù) A 與遞歸判斷的總遞歸深度為 M ；當(dāng) M>N 時(shí)，最差情況為遍歷至樹(shù) A 葉子節(jié)點(diǎn)，此時(shí)總遞歸深度為 M。

END

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強(qiáng)！

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。