##題目描述 輸入兩棵二叉樹A，B，判斷B是不是A的子結構，（ps：我們約定空樹不是任意一個樹的子結構）
思路
因為題解的特殊邊界問題和搜索樹時的跨層問題，需要將遞回拆分和改造，
時間復雜度O(n)，空間復雜度O(n)，
代碼
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private boolean isSubTree(TreeNode A,TreeNode B, int deep) {
if(B == null) return true;
if(A == null) return false;
boolean flag = false;
if(A.val == B.val) {
// deep引數解決遞回搜索時的跨層搜索問題
flag = isSubTree(A.left, B.left, 2) && isSubTree(A.right, B.right, 2);
}
// 僅當兩樹比對進行到第一層并不滿足相等時，才搜索A的子樹
// 若比對進行到非第一層，出現val不等則false
if(!flag && deep == 1) {
flag = isSubTree(A.left, B, 1) || isSubTree(A.right, B, 1);
}
return flag;
}
public boolean HasSubtree(TreeNode A, TreeNode B) {
boolean flag = false;
//遞回出口的判斷依賴于A、B的非空情況，根據題目ps的特殊要求，需要A、B都不空再遞回
if(A != null && B != null) {
flag = isSubTree(A, B, 1);
}
return flag;
}
}
筆記
樹的邊界問題，跨層搜索問題可以通過遞回攜帶deep解決，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/86931.html
標籤：其他
上一篇：合并兩個排序的鏈表