我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題原始碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 面試題26. 樹的子結構
題目
輸入兩棵二叉樹A和B，判斷B是不是A的子結構，(約定空樹不是任意一個樹的子結構)
B是A的子結構， 即 A中有出現和B相同的結構和節點值，
例如:
給定的樹 A:
3
/ \
4 5
/ \
1 2
給定的樹 B：
4
/
1
回傳 true，因為 B 與 A 的一個子樹擁有相同的結構和節點值，
示例 1：
輸入：A = [1,2,3], B = [3,1]
輸出：false
示例 2：
輸入：A = [3,4,5,1,2], B = [4,1]
輸出：true
限制：
- 0 <= 節點個數 <= 10000
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路
與本題相似的題目，可對比學習：
- LeetCode 572. 另一個樹的子樹
思路1-遞回校驗B是否是A的一部分或是A某子樹的一部分
步驟：
- B是否是A的一部分，若為false則進入第2步，否則結束；
- B是否是A某子樹的一部分，遞回處理直至某一層回傳true或遞回處理完所有節點；
演算法復雜度: M為A的總節點數，N為B的節點數
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(M * N\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(max(M, N)\right)}} $
演算法原始碼示例
package leetcode;
/**
* @author ZhouJie
* @date 2020年5月22日 下午6:03:04
* @Description: 面試題26. 樹的子結構
*
*/
public class LeetCode_Offer_26 {
}
// Definition for a binary tree node.
class TreeNode_Offer_26 {
int val;
TreeNode_Offer_26 left;
TreeNode_Offer_26 right;
TreeNode_Offer_26(int x) {
val = x;
}
}
class Solution_Offer_26 {
/**
* @author: ZhouJie
* @date: 2020年5月22日 下午6:07:38
* @param: @param A
* @param: @param B
* @param: @return
* @return: boolean
* @Description: 1-遞回校驗B是否是A本身或是A某子樹的一部分
*
*/
public boolean isSubStructure(TreeNode_Offer_26 A, TreeNode_Offer_26 B) {
if (A == null && B == null) {
return true;
} else if (A != null && B != null) {
// t可能是s本身或者是s的左子樹/右子樹
return checkSubtree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
} else {
return false;
}
}
/**
* @author: ZhouJie
* @date: 2020年5月22日 下午6:07:56
* @param: @param A
* @param: @param B
* @param: @return
* @return: boolean
* @Description: 判斷B是否是A某子樹的一部分
*
*/
private boolean checkSubtree(TreeNode_Offer_26 A, TreeNode_Offer_26 B) {
// 此時t可以為null，表明t已經處理完，s是否為null已無所謂
if (B == null) {
return true;
// 此時t不為null，那么s也必須不為null，且值也必須相等
} else if (A != null && B != null && A.val == B.val) {
return checkSubtree(A.left, B.left) && checkSubtree(A.right, B.right);
} else {
return false;
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/185230.html
標籤：Java
下一篇：java 類加載系統