小編給大家分享一下LeetCode如何實(shí)現(xiàn)樹的子結(jié)構(gòu),相信大部分人都還不怎么了解,因此分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后大有收獲,下面讓我們一起去了解一下吧!
創(chuàng)新互聯(lián)長期為上1000+客戶提供的網(wǎng)站建設(shè)服務(wù),團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年,關(guān)注不同地域、不同群體,并針對不同對象提供差異化的產(chǎn)品和服務(wù);打造開放共贏平臺,與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為貢嘎企業(yè)提供專業(yè)的網(wǎng)站設(shè)計(jì)制作、網(wǎng)站設(shè)計(jì),貢嘎網(wǎng)站改版等技術(shù)服務(wù)。擁有十載豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。
輸入兩棵二叉樹 A 和 B,判斷 B 是不是 A 的子結(jié)構(gòu)。(約定空樹不是任意一個(gè)樹的子結(jié)構(gòu))
B 是 A 的子結(jié)構(gòu), 即 A 中有出現(xiàn)和 B 相同的結(jié)構(gòu)和節(jié)點(diǎn)值。
例如: 給定的樹 A:
3
/ \
4 5
/ \
1 2
給定的樹 B:
4
/
1
返回 true,因?yàn)?B 與 A 的一個(gè)子樹擁有相同的結(jié)構(gòu)和節(jié)點(diǎn)值。
0 <= 節(jié)點(diǎn)個(gè)數(shù) <= 10000
A = [1,2,3], B = [3,1]
false
A = [3,4,5,1,2], B = [4,1]
true
O(MN)
O(MN)
O(M)
O(M)
遞歸??臻g, match 遞歸調(diào)用使用
O(min(M, N))
遞歸棧空間, 所以整體空間復(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:
# 因?yàn)锳的子樹部分可以有部分節(jié)點(diǎn)是B沒有的, 所以如果當(dāng)前b節(jié)點(diǎ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í)各自左右子樹部分也要匹配
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)
以上是“LeetCode如何實(shí)現(xiàn)樹的子結(jié)構(gòu)”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內(nèi)容對大家有所幫助,如果還想學(xué)習(xí)更多知識,歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道!
文章名稱:LeetCode如何判斷樹的子結(jié)構(gòu)
網(wǎng)頁URL:http://bm7419.com/article14/iidpde.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供電子商務(wù)、移動網(wǎng)站建設(shè)、網(wǎng)站內(nèi)鏈、網(wǎng)站設(shè)計(jì)、微信小程序、品牌網(wǎng)站制作
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來源: 創(chuàng)新互聯(lián)