題目
輸入兩棵二叉樹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é)點值。
示例 1：
輸入：A = [1,2,3], B = [3,1]
輸出：false
示例 2：
輸入：A = [3,4,5,1,2], B = [4,1]
輸出：true
限制：
0 <= 節(jié)點個數(shù) <= 10000
解題思路
1.題目要求我們判斷B是不是A的子結(jié)構(gòu)，我們用遞歸來解決這個問題。
2.二叉樹 B 為 A 的子結(jié)構(gòu)的情況一共有三種，滿足其中一種即可：
①子結(jié)構(gòu) B 的起點為 A 的根節(jié)點，即從 A 的根節(jié)點開始和 B 比較， 調(diào)用函數(shù) isSubStree:
- 不相等，則返回 false;
- 相等，則再比較 左子樹和右子樹都是否相等，都相等，才返回 true
②子結(jié)構(gòu) B 在 A 的左子樹中，即 B 的起點隱藏在 A 的左子樹中，此時調(diào)用函數(shù) isSubStructure；
③子結(jié)構(gòu) B 在 A 的右子樹中，即 B 的起點隱藏在 A 的右子樹中，此時調(diào)用函數(shù) isSubStructure。3.舉個例子：
我們先從 A 的根節(jié)點開始和 B 比較，調(diào)用函數(shù) isSubStree:
根節(jié)點相等，則再比較 左子樹和右子樹都是否相等，都不1相等，返回 false。
?我們猜測子結(jié)構(gòu) B 在 A 的左子樹中，即 B 的起點隱藏在 A 的左子樹中，此時調(diào)用函數(shù) isSubStructure
?在左子樹中調(diào)用函數(shù) isSubStree，根節(jié)點都不同則返回 false;再往左子樹走，
?依舊不同，此時我們返回上一級，去看看右子樹
也不同，此時A的左子樹全部檢索完畢，我們需要檢索右子樹
?這時我們調(diào)用函數(shù) isSubStree，根節(jié)點相等，則再比較 左子樹和右子樹都是否相等，都相等，返回 true。代表我們找到了子結(jié)構(gòu)。
?文章來源地址http://www.zghlxwxcb.cn/news/detail-645215.html
代碼實現(xiàn)
lass Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if(A == null || B == null){
return false;
}
if(isSubTree(A, B)){
return true;
}
if(isSubStructure(A.left, B) || isSubStructure(A.right, B)){
return true;
}
return false;
}
boolean isSubTree(TreeNode TA, TreeNode TB){
if(TB == null){
return true;
}
if(TA == null){
return false;
}
if(TB.val != TA.val){
return false;
}
return isSubTree(TA.left , TB.left) &&
isSubTree(TA.right, TB.right);
}
}測試結(jié)果
文章來源：http://www.zghlxwxcb.cn/news/detail-645215.html
?
到了這里，關(guān)于Leetcode-每日一題【劍指 Offer 26. 樹的子結(jié)構(gòu)】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
