廢話不多說，喊一句號(hào)子鼓勵(lì)自己：程序員永不失業(yè)，程序員走向架構(gòu)！本篇Blog的主題是【子結(jié)構(gòu)】，使用【二叉樹】這個(gè)基本的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，這個(gè)高頻題的站點(diǎn)是：CodeTop，篩選條件為：目標(biāo)公司+最近一年+出現(xiàn)頻率排序，由高到低的去?？蚑OP101去找，只有兩個(gè)地方都出現(xiàn)過才做這道題（CodeTop本身匯聚了LeetCode的來源），確保刷的題都是高頻要面試考的題。
明確目標(biāo)題后，附上題目鏈接，后期可以依據(jù)解題思路反復(fù)快速練習(xí)，題目按照題干的基本數(shù)據(jù)結(jié)構(gòu)分類，且每個(gè)分類的第一篇必定是對基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的介紹。
樹的子結(jié)構(gòu)【MID】
雙重遞歸，前所未有的體驗(yàn)
題干
直接粘題干和用例
解題思路
原題解地址，若樹 B 是樹 A 的子結(jié)構(gòu)，則子結(jié)構(gòu)的根節(jié)點(diǎn)可能為樹 A 的任意一個(gè)節(jié)點(diǎn)。因此，判斷樹 B 是否是樹 A 的子結(jié)構(gòu)，需完成以下兩步工作：
- 先序遍歷樹 A 中的每個(gè)節(jié)點(diǎn) node ；（對應(yīng)函數(shù)
isSubStructure(A, B)） - 判斷樹 A 中以 node 為根節(jié)點(diǎn)的子樹是否包含樹 B 。（
對應(yīng)函數(shù) recur(A, B)）
樹 A 的根節(jié)點(diǎn)記作 節(jié)點(diǎn) A ，樹 B 的根節(jié)點(diǎn)稱為 節(jié)點(diǎn) B 。
recur(A, B) 函數(shù)：
終止條件：
- 當(dāng)節(jié)點(diǎn) B 為空：說明樹 B 已匹配完成（越過葉子節(jié)點(diǎn)），因此返回 true ；
- 當(dāng)節(jié)點(diǎn) A 為空：說明已經(jīng)越過樹 A 的葉節(jié)點(diǎn)，即匹配失敗，返回 false；
- 當(dāng)節(jié)點(diǎn) A 和 B 的值不同：說明匹配失敗，返回 false ；
返回值：
- 判斷 A 和 B 的 左子節(jié)點(diǎn) 是否相等，即
recur(A.left, B.left)； - 判斷 A 和 B 的 右子節(jié)點(diǎn) 是否相等，即
recur(A.right, B.right)；
isSubStructure(A, B) 函數(shù)：
特例處理： 當(dāng) 樹 A 為空 或 樹 B 為空 時(shí)，直接返回 false；
返回值： 若樹 B 是樹 A 的子結(jié)構(gòu)，則必滿足以下三種情況之一，因此用或 || 連接；
- 以 節(jié)點(diǎn) A 為根節(jié)點(diǎn)的子樹 包含樹 B ，對應(yīng) recur(A, B)；
- 樹 B 是 樹 A 左子樹 的子結(jié)構(gòu)，對應(yīng)
isSubStructure(A.left, B)； - 樹 B 是 樹 A 右子樹 的子結(jié)構(gòu)，對應(yīng)
isSubStructure(A.right, B)；
代碼實(shí)現(xiàn)
給出代碼實(shí)現(xiàn)基本檔案
基本數(shù)據(jù)結(jié)構(gòu)：二叉樹
輔助數(shù)據(jù)結(jié)構(gòu)：無
算法：遞歸
技巧：無
其中數(shù)據(jù)結(jié)構(gòu)、算法和技巧分別來自：文章來源：http://www.zghlxwxcb.cn/news/detail-727681.html
- 10 個(gè)數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、棧、隊(duì)列、散列表、二叉樹、堆、跳表、圖、Trie 樹
- 10 個(gè)算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動(dòng)態(tài)規(guī)劃、字符串匹配算法
- 技巧：雙指針、滑動(dòng)窗口、中心擴(kuò)散
當(dāng)然包括但不限于以上文章來源地址http://www.zghlxwxcb.cn/news/detail-727681.html
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
/**
* 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
*
*
* @param n int整型 the n
* @return int整型
*/
public boolean isSubStructure(TreeNode A, TreeNode B) {
// 1 如果A樹或B樹為空，則匹配失敗
if (A == null || B == null) {
return false;
}
// 2 A的當(dāng)前節(jié)點(diǎn)包含B，或A的左子樹包含B，或A的右子樹包含B
return isNodeSub(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
private boolean isNodeSub(TreeNode node, TreeNode B) {
// 1 如果B為空，說明B節(jié)點(diǎn)比對完成，匹配成功【終止條件】
if (B == null ) {
return true;
}
// 2 如果B不為null，且node為空，說明尚未匹配完B但已越過A的節(jié)點(diǎn)樹葉子節(jié)點(diǎn)，匹配失敗【終止條件】
if (node == null ) {
return false;
}
// 3 如果node節(jié)點(diǎn)值不等于B，則說明不是子結(jié)構(gòu)，匹配失敗【本層任務(wù)】
if (node.val != B.val) {
return false;
}
// 4 比較node與B的左右子節(jié)點(diǎn),必須都滿足條件才可以【返回值】
return isNodeSub(node.left, B.left) && isNodeSub(node.right, B.right);
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度 O(MN)： 其中 M,N分別為樹 A 和 樹 B 的節(jié)點(diǎn)數(shù)量；先序遍歷樹 A 占用 O(M) ，每次調(diào)用
recur(A, B)判斷占用 O(N)。 - 空間復(fù)雜度 O(M) ： 當(dāng)樹 A 和樹 B 都退化為鏈表時(shí)，遞歸調(diào)用的深度取決于二叉樹A的高度，最壞情況下，二叉樹A是一個(gè)完全不平衡的樹，高度為M，因此遞歸調(diào)用的最大深度為M。每次遞歸調(diào)用都需要一些額外的?？臻g來保存函數(shù)調(diào)用的上下文，因此空間復(fù)雜度為O(M)
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)-二叉樹 九】【樹的子結(jié)構(gòu)】：樹的子結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
