這篇文章主要為大家展示了“LeetCode中怎么判斷樹(shù)的子結(jié)構(gòu)”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“LeetCode中怎么判斷樹(shù)的子結(jié)構(gòu)”這篇文章吧。
創(chuàng)新互聯(lián)建站專(zhuān)注為客戶(hù)提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都網(wǎng)站建設(shè)、網(wǎng)站制作、大安網(wǎng)絡(luò)推廣、小程序定制開(kāi)發(fā)、大安網(wǎng)絡(luò)營(yíng)銷(xiāo)、大安企業(yè)策劃、大安品牌公關(guān)、搜索引擎seo、人物專(zhuān)訪(fǎng)、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等，從售前售中售后，我們都將竭誠(chéng)為您服務(wù)，您的肯定，是我們最大的嘉獎(jiǎng)；創(chuàng)新互聯(lián)建站為所有大學(xué)生創(chuàng)業(yè)者提供大安建站搭建服務(wù)，24小時(shí)服務(wù)熱線(xiàn)：13518219792，官方網(wǎng)址：www.cdcxhl.com
問(wèn)題描述
輸入兩棵二叉樹(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)值。
示例 1：
輸入：A = [1,2,3], B = [3,1]
輸出：false
示例 2：
輸入：A = [3,4,5,1,2], B = [4,1]
輸出：true
限制：
0 <= 節(jié)點(diǎn)個(gè)數(shù) <= 10000
問(wèn)題分析
要判斷B是否是A的子結(jié)構(gòu)，像下面這樣，我們只需要從根節(jié)點(diǎn)開(kāi)始判斷，通過(guò)遞歸的方式比較他的每一個(gè)子節(jié)點(diǎn)即可，所以代碼也很容易寫(xiě)
重慶分公司
重慶分公司
1public boolean isSubStructure(TreeNode A, TreeNode B) {
2 //邊界條件判斷，如果A和B有一個(gè)為空，返回false
3 if (A == null || B == null)
4 return false;
5 return isSub(A, B);
6}
7
8boolean isSub(TreeNode A, TreeNode B) {
9 //這里如果B為空，說(shuō)明B已經(jīng)訪(fǎng)問(wèn)完了，確定是A的子結(jié)構(gòu)
10 if (B == null)
11 return true;
12 //如果B不為空A為空，或者這兩個(gè)節(jié)點(diǎn)值不同，說(shuō)明B樹(shù)不是
13 //A的子結(jié)構(gòu)，直接返回false
14 if (A == null || A.val != B.val)
15 return false;
16 //當(dāng)前節(jié)點(diǎn)比較完之后還要繼續(xù)判斷左右子節(jié)點(diǎn)
17 return isSub(A.left, B.left) && isSub(A.right, B.right);
18}
但實(shí)際上B如果是A的子結(jié)構(gòu)的話(huà)，不一定是從根節(jié)點(diǎn)開(kāi)始的，也可能是下面這樣
也就是說(shuō)B不光有可能是A的子結(jié)構(gòu)，也有可能是A左子樹(shù)的子結(jié)構(gòu)或者右子樹(shù)的子結(jié)構(gòu)，所以如果從根節(jié)點(diǎn)判斷B不是A的子結(jié)構(gòu)，還要繼續(xù)判斷B是不是A左子樹(shù)的子結(jié)構(gòu)和右子樹(shù)的子結(jié)構(gòu)，代碼如下
1public boolean isSubStructure(TreeNode A, TreeNode B) {
2 if (A == null || B == null)
3 return false;
4 //先從根節(jié)點(diǎn)判斷B是不是A的子結(jié)構(gòu)，如果不是在分別從左右兩個(gè)子樹(shù)判斷，
5 //只要有一個(gè)為true，就說(shuō)明B是A的子結(jié)構(gòu)
6 return isSub(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
7}
8
9boolean isSub(TreeNode A, TreeNode B) {
10 //這里如果B為空，說(shuō)明B已經(jīng)訪(fǎng)問(wèn)完了，確定是A的子結(jié)構(gòu)
11 if (B == null)
12 return true;
13 //如果B不為空A為空，或者這兩個(gè)節(jié)點(diǎn)值不同，說(shuō)明B樹(shù)不是
14 //A的子結(jié)構(gòu)，直接返回false
15 if (A == null || A.val != B.val)
16 return false;
17 //當(dāng)前節(jié)點(diǎn)比較完之后還要繼續(xù)判斷左右子節(jié)點(diǎn)
18 return isSub(A.left, B.left) && isSub(A.right, B.right);
19}以上是“LeetCode中怎么判斷樹(shù)的子結(jié)構(gòu)”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！
