實現(xiàn)二叉樹子結(jié)構(gòu)匹配)
CS-Notes 劍指 Offer 第 26 題詳解用兩段遞歸類函數(shù)實現(xiàn)二叉樹子結(jié)構(gòu)匹配【免費下載鏈接】CS-Notes:books: 技術(shù)面試必備基礎(chǔ)知識、Leetcode、計算機操作系統(tǒng)、計算機網(wǎng)絡(luò)、系統(tǒng)設(shè)計項目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本文基于 CS-Notes 倉庫中 劍指 Offer 題解 - 樹的子結(jié)構(gòu) 一文展開完整繼承其題目描述與官方解法代碼并結(jié)合該倉庫其他樹類題解如 二叉樹的鏡像、對稱的二叉樹中的同構(gòu)遞歸套路深入剖析“子結(jié)構(gòu)判定”的兩段式遞歸設(shè)計、空樹邊界的語義約定以及復(fù)雜度與易錯點幫助讀者掌握二叉樹模式匹配類面試題的標(biāo)準解法與變形思路。題目描述劍指 Offer 第 26 題“樹的子結(jié)構(gòu)”的原始定義如下輸入兩棵二叉樹 A 和 B判斷 B 是不是 A 的子結(jié)構(gòu)。約定空樹不是任意樹的子結(jié)構(gòu)即空樹不算作 A 的子結(jié)構(gòu)。直觀示例如下圖所示樹root2右圖是否是樹root1左圖的子結(jié)構(gòu)。在《劍指 Offer》的解題約定中“B 是 A 的子結(jié)構(gòu)”需要滿足一個結(jié)構(gòu)性條件存在 A 中的某個節(jié)點 N使得以 N 為根的子樹與 B 的結(jié)構(gòu)一致對應(yīng)節(jié)點值相等且 B 中不存在的子節(jié)點不影響判定——也就是說匹配只要求 B 中已有的節(jié)點在 A 的對應(yīng)位置上找到值相等的節(jié)點B 中為空的分支不要求 A 中也為空。這一約定是理解后續(xù)代碼中所有終止條件的關(guān)鍵。核心思路全局搜索 局部驗證的兩段式遞歸子結(jié)構(gòu)判定天然可以拆解為兩個相互遞歸的子問題這也是該題解法代碼中兩個函數(shù)的分工全局搜索HasSubtree以root1的每一個節(jié)點為候選起點嘗試讓root2從該節(jié)點開始匹配。若當(dāng)前節(jié)點匹配成功則返回 true否則依次退回其左子樹、右子樹繼續(xù)搜索局部驗證isSubtreeWithRoot假設(shè)兩棵樹的當(dāng)前根節(jié)點已經(jīng)對齊逐層向下驗證“以root2當(dāng)前節(jié)點為根的結(jié)構(gòu)是否完全被root1對應(yīng)位置覆蓋”。兩者形成經(jīng)典的“外層遍歷候選根、內(nèi)層驗證匹配”模式與 對稱的二叉樹 中“雙指針同步下探兩棵樹”、二叉樹的鏡像 中“前序遞歸交換”屬于同一族“對兩棵或同一棵的樹做同步遞歸”的套路。完整解法代碼與逐行解析以下代碼完整來自倉庫原文檔 26. 樹的子結(jié)構(gòu)是?？途W(wǎng)在線判題環(huán)境下的標(biāo)準 Java 實現(xiàn)public boolean HasSubtree(TreeNode root1, TreeNode root2) { if (root1 null || root2 null) return false; return isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2); } private boolean isSubtreeWithRoot(TreeNode root1, TreeNode root2) { if (root2 null) return true; if (root1 null) return false; if (root1.val ! root2.val) return false; return isSubtreeWithRoot(root1.left, root2.left) isSubtreeWithRoot(root1.right, root2.right); }逐行說明入口防御root1 null || root2 null時直接返回 false。root1為空說明沒有候選起點自然不存在子結(jié)構(gòu)root2為空時此實現(xiàn)也返回 false等價于采用了“空樹不是任意樹子結(jié)構(gòu)”的判題口徑見下一節(jié)對兩種約定的討論。短路求值的候選遍歷isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2)一行完成了“先驗證當(dāng)前根、再向左右子樹擴散”的全局搜索。||的短路特性保證一旦某個起點驗證成功后續(xù)子樹不再被訪問平均情況下可以提前退出。內(nèi)層驗證的三種終止root2 null返回 true表示root2的結(jié)構(gòu)已經(jīng)全部匹配完畢剩下root1側(cè)多出的節(jié)點不影響結(jié)論——這正是“子結(jié)構(gòu)”區(qū)別于“兩棵樹完全相同”的語義所在root1 null返回 falseroot2還有剩余結(jié)構(gòu)但root1側(cè)已經(jīng)沒有節(jié)點可對應(yīng)驗證失敗節(jié)點值不等返回 false結(jié)構(gòu)對齊的前提是值相等一旦不等立即剪枝遞歸下探值相等時同時遞歸左右兩側(cè)任何一側(cè)失敗即整體失敗與 對稱的二叉樹 中isSymmetrical(t1.left, t2.right) isSymmetrical(t1.right, t2.left)的同步下探寫法結(jié)構(gòu)一致?？諛湔Z義約定為什么兩處空判斷“一真一假”讀這段代碼時最容易產(chǎn)生疑問的是同為遇到空節(jié)點HasSubtree里root2 null返回 false而isSubtreeWithRoot里root2 null卻返回 true。這兩處并不矛盾而是分別服務(wù)于不同的判定時機入口處HasSubtree第一行root2作為整體輸入就是空樹。按《劍指 Offer》的題目約定空樹不被認為是任何樹的子結(jié)構(gòu)因此直接拒絕避免把“空對非空”誤判為成功驗證過程中isSubtreeWithRoot第一行root2是在遞歸下探途中“用完了”即它的剩余部分已經(jīng)與root1的某個子樹逐節(jié)點匹配完畢返回 true 是“匹配完成”的正常收尾而不是“空樹等于任意樹”。這種組合使代碼同時兼容兩種常見判題口徑若采用《劍指 Offer》2019 版/LeetCode 572 風(fēng)格空樹不算子結(jié)構(gòu)入口的root2 null分支已經(jīng)兜底若采用“空樹是任意樹子結(jié)構(gòu)”的寬松定義只需將入口處的root2 null改為返回 true 即可內(nèi)層驗證邏輯保持不變。理解這一點對后續(xù)應(yīng)對面試官追問“空樹怎么處理”至關(guān)重要。復(fù)雜度分析設(shè)root1的節(jié)點數(shù)為 Mroot2的節(jié)點數(shù)為 N時間復(fù)雜度最壞情況下root1的每個節(jié)點都會觸發(fā)一次對root2的完整結(jié)構(gòu)驗證例如所有節(jié)點值都相同、直到深處才出現(xiàn)結(jié)構(gòu)差異總代價為 O(M×N)由于短路求值平均情況下實際訪問的節(jié)點對遠小于 M×N空間復(fù)雜度僅來自遞歸調(diào)用棧外層搜索深度最深 M 層內(nèi)層驗證深度最深 N 層合計 O(M N)。對于面試中更常見的中等規(guī)模輸入該遞歸解法已經(jīng)足夠題目本身也未要求優(yōu)化到線性級別重點在于把遞歸邊界講清楚。邊界與易錯點清單root2只有一側(cè)子樹如root2根節(jié)點只有左孩子驗證root1對應(yīng)節(jié)點時其右孩子可以為空也可以非空內(nèi)層遞歸對root2.right null直接返回 true這是“子結(jié)構(gòu)”而非“相等子樹”的直接體現(xiàn)值相等但結(jié)構(gòu)不同isSubtreeWithRoot會因在第一個結(jié)構(gòu)不匹配的分支立刻返回 false不會繼續(xù)浪費搜索單節(jié)點樹root1、root2都只有一個節(jié)點且值相等時兩側(cè)遞歸均在root2 null處返回 true結(jié)果為 true值不等則入口比較即失敗常見寫法錯誤把內(nèi)層驗證的root2 null誤寫為 false、或忘記入口對root1 null的防御雖然isSubtreeWithRoot能處理root1為空但入口提前剪枝可避免一次無意義的調(diào)用。與同類題的關(guān)系及延伸若把判定條件從“子結(jié)構(gòu)”收緊為“完全相同的子樹”則只需將isSubtreeWithRoot中root2 null的返回值由 true 改為root1 null其余搜索框架不變即得到 LeetCode 572“另一棵樹的子樹”的判定方式該題不認為空樹是子樹入口對root2 null返回 false 與其口徑一致若 B 是有序序列而 A 是二叉樹則演變?yōu)椤膀炞C前序/后序序列是否對應(yīng)樹結(jié)構(gòu)”一類問題可參考倉庫中 7. 重建二叉樹 對“遍歷序列與樹結(jié)構(gòu)互推”的分析遞歸同步下探兩棵樹的模板還出現(xiàn)在 28. 對稱的二叉樹對稱即“左子樹與右子樹互為鏡像”中掌握本節(jié)兩段式結(jié)構(gòu)后這類題基本是同構(gòu)替換更多二叉樹面試題層序打印、路徑和等可在 劍指 Offer 題解 - 目錄 的“樹”分類下按題號繼續(xù)學(xué)習(xí)。小結(jié)樹的子結(jié)構(gòu)一題的精髓在于把“匹配”與“搜索”拆成兩個遞歸函數(shù)外層HasSubtree負責(zé)在root1上枚舉所有候選根并借助短路求值提前退出內(nèi)層isSubtreeWithRoot負責(zé)在根對齊的前提下逐節(jié)點驗證并用root2 null → true表達“結(jié)構(gòu)已匹配完整”的語義。理解入口空樹防御與驗證過程空樹收尾這兩處空判斷的分工是該題答到面試官點頭的關(guān)鍵再結(jié)合 O(M×N) 最壞時間的復(fù)雜度說明即可完成一次完整而嚴謹?shù)淖鞔??！久赓M下載鏈接】CS-Notes:books: 技術(shù)面試必備基礎(chǔ)知識、Leetcode、計算機操作系統(tǒng)、計算機網(wǎng)絡(luò)、系統(tǒng)設(shè)計項目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考 CS-Notes 劍指 Offer 第 26 題詳解：用兩段遞歸類函數(shù)實現(xiàn)二叉樹子結(jié)構(gòu)匹配
CS-Notes 劍指 Offer 第 26 題詳解用兩段遞歸類函數(shù)實現(xiàn)二叉樹子結(jié)構(gòu)匹配【免費下載鏈接】CS-Notes:books: 技術(shù)面試必備基礎(chǔ)知識、Leetcode、計算機操作系統(tǒng)、計算機網(wǎng)絡(luò)、系統(tǒng)設(shè)計項目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本文基于 CS-Notes 倉庫中 劍指 Offer 題解 - 樹的子結(jié)構(gòu) 一文展開完整繼承其題目描述與官方解法代碼并結(jié)合該倉庫其他樹類題解如 二叉樹的鏡像、對稱的二叉樹中的同構(gòu)遞歸套路深入剖析“子結(jié)構(gòu)判定”的兩段式遞歸設(shè)計、空樹邊界的語義約定以及復(fù)雜度與易錯點幫助讀者掌握二叉樹模式匹配類面試題的標(biāo)準解法與變形思路。題目描述劍指 Offer 第 26 題“樹的子結(jié)構(gòu)”的原始定義如下輸入兩棵二叉樹 A 和 B判斷 B 是不是 A 的子結(jié)構(gòu)。約定空樹不是任意樹的子結(jié)構(gòu)即空樹不算作 A 的子結(jié)構(gòu)。直觀示例如下圖所示樹root2右圖是否是樹root1左圖的子結(jié)構(gòu)。在《劍指 Offer》的解題約定中“B 是 A 的子結(jié)構(gòu)”需要滿足一個結(jié)構(gòu)性條件存在 A 中的某個節(jié)點 N使得以 N 為根的子樹與 B 的結(jié)構(gòu)一致對應(yīng)節(jié)點值相等且 B 中不存在的子節(jié)點不影響判定——也就是說匹配只要求 B 中已有的節(jié)點在 A 的對應(yīng)位置上找到值相等的節(jié)點B 中為空的分支不要求 A 中也為空。這一約定是理解后續(xù)代碼中所有終止條件的關(guān)鍵。核心思路全局搜索 局部驗證的兩段式遞歸子結(jié)構(gòu)判定天然可以拆解為兩個相互遞歸的子問題這也是該題解法代碼中兩個函數(shù)的分工全局搜索HasSubtree以root1的每一個節(jié)點為候選起點嘗試讓root2從該節(jié)點開始匹配。若當(dāng)前節(jié)點匹配成功則返回 true否則依次退回其左子樹、右子樹繼續(xù)搜索局部驗證isSubtreeWithRoot假設(shè)兩棵樹的當(dāng)前根節(jié)點已經(jīng)對齊逐層向下驗證“以root2當(dāng)前節(jié)點為根的結(jié)構(gòu)是否完全被root1對應(yīng)位置覆蓋”。兩者形成經(jīng)典的“外層遍歷候選根、內(nèi)層驗證匹配”模式與 對稱的二叉樹 中“雙指針同步下探兩棵樹”、二叉樹的鏡像 中“前序遞歸交換”屬于同一族“對兩棵或同一棵的樹做同步遞歸”的套路。完整解法代碼與逐行解析以下代碼完整來自倉庫原文檔 26. 樹的子結(jié)構(gòu)是?？途W(wǎng)在線判題環(huán)境下的標(biāo)準 Java 實現(xiàn)public boolean HasSubtree(TreeNode root1, TreeNode root2) { if (root1 null || root2 null) return false; return isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2); } private boolean isSubtreeWithRoot(TreeNode root1, TreeNode root2) { if (root2 null) return true; if (root1 null) return false; if (root1.val ! root2.val) return false; return isSubtreeWithRoot(root1.left, root2.left) isSubtreeWithRoot(root1.right, root2.right); }逐行說明入口防御root1 null || root2 null時直接返回 false。root1為空說明沒有候選起點自然不存在子結(jié)構(gòu)root2為空時此實現(xiàn)也返回 false等價于采用了“空樹不是任意樹子結(jié)構(gòu)”的判題口徑見下一節(jié)對兩種約定的討論。短路求值的候選遍歷isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2)一行完成了“先驗證當(dāng)前根、再向左右子樹擴散”的全局搜索。||的短路特性保證一旦某個起點驗證成功后續(xù)子樹不再被訪問平均情況下可以提前退出。內(nèi)層驗證的三種終止root2 null返回 true表示root2的結(jié)構(gòu)已經(jīng)全部匹配完畢剩下root1側(cè)多出的節(jié)點不影響結(jié)論——這正是“子結(jié)構(gòu)”區(qū)別于“兩棵樹完全相同”的語義所在root1 null返回 falseroot2還有剩余結(jié)構(gòu)但root1側(cè)已經(jīng)沒有節(jié)點可對應(yīng)驗證失敗節(jié)點值不等返回 false結(jié)構(gòu)對齊的前提是值相等一旦不等立即剪枝遞歸下探值相等時同時遞歸左右兩側(cè)任何一側(cè)失敗即整體失敗與 對稱的二叉樹 中isSymmetrical(t1.left, t2.right) isSymmetrical(t1.right, t2.left)的同步下探寫法結(jié)構(gòu)一致?？諛湔Z義約定為什么兩處空判斷“一真一假”讀這段代碼時最容易產(chǎn)生疑問的是同為遇到空節(jié)點HasSubtree里root2 null返回 false而isSubtreeWithRoot里root2 null卻返回 true。這兩處并不矛盾而是分別服務(wù)于不同的判定時機入口處HasSubtree第一行root2作為整體輸入就是空樹。按《劍指 Offer》的題目約定空樹不被認為是任何樹的子結(jié)構(gòu)因此直接拒絕避免把“空對非空”誤判為成功驗證過程中isSubtreeWithRoot第一行root2是在遞歸下探途中“用完了”即它的剩余部分已經(jīng)與root1的某個子樹逐節(jié)點匹配完畢返回 true 是“匹配完成”的正常收尾而不是“空樹等于任意樹”。這種組合使代碼同時兼容兩種常見判題口徑若采用《劍指 Offer》2019 版/LeetCode 572 風(fēng)格空樹不算子結(jié)構(gòu)入口的root2 null分支已經(jīng)兜底若采用“空樹是任意樹子結(jié)構(gòu)”的寬松定義只需將入口處的root2 null改為返回 true 即可內(nèi)層驗證邏輯保持不變。理解這一點對后續(xù)應(yīng)對面試官追問“空樹怎么處理”至關(guān)重要。復(fù)雜度分析設(shè)root1的節(jié)點數(shù)為 Mroot2的節(jié)點數(shù)為 N時間復(fù)雜度最壞情況下root1的每個節(jié)點都會觸發(fā)一次對root2的完整結(jié)構(gòu)驗證例如所有節(jié)點值都相同、直到深處才出現(xiàn)結(jié)構(gòu)差異總代價為 O(M×N)由于短路求值平均情況下實際訪問的節(jié)點對遠小于 M×N空間復(fù)雜度僅來自遞歸調(diào)用棧外層搜索深度最深 M 層內(nèi)層驗證深度最深 N 層合計 O(M N)。對于面試中更常見的中等規(guī)模輸入該遞歸解法已經(jīng)足夠題目本身也未要求優(yōu)化到線性級別重點在于把遞歸邊界講清楚。邊界與易錯點清單root2只有一側(cè)子樹如root2根節(jié)點只有左孩子驗證root1對應(yīng)節(jié)點時其右孩子可以為空也可以非空內(nèi)層遞歸對root2.right null直接返回 true這是“子結(jié)構(gòu)”而非“相等子樹”的直接體現(xiàn)值相等但結(jié)構(gòu)不同isSubtreeWithRoot會因在第一個結(jié)構(gòu)不匹配的分支立刻返回 false不會繼續(xù)浪費搜索單節(jié)點樹root1、root2都只有一個節(jié)點且值相等時兩側(cè)遞歸均在root2 null處返回 true結(jié)果為 true值不等則入口比較即失敗常見寫法錯誤把內(nèi)層驗證的root2 null誤寫為 false、或忘記入口對root1 null的防御雖然isSubtreeWithRoot能處理root1為空但入口提前剪枝可避免一次無意義的調(diào)用。與同類題的關(guān)系及延伸若把判定條件從“子結(jié)構(gòu)”收緊為“完全相同的子樹”則只需將isSubtreeWithRoot中root2 null的返回值由 true 改為root1 null其余搜索框架不變即得到 LeetCode 572“另一棵樹的子樹”的判定方式該題不認為空樹是子樹入口對root2 null返回 false 與其口徑一致若 B 是有序序列而 A 是二叉樹則演變?yōu)椤膀炞C前序/后序序列是否對應(yīng)樹結(jié)構(gòu)”一類問題可參考倉庫中 7. 重建二叉樹 對“遍歷序列與樹結(jié)構(gòu)互推”的分析遞歸同步下探兩棵樹的模板還出現(xiàn)在 28. 對稱的二叉樹對稱即“左子樹與右子樹互為鏡像”中掌握本節(jié)兩段式結(jié)構(gòu)后這類題基本是同構(gòu)替換更多二叉樹面試題層序打印、路徑和等可在 劍指 Offer 題解 - 目錄 的“樹”分類下按題號繼續(xù)學(xué)習(xí)。小結(jié)樹的子結(jié)構(gòu)一題的精髓在于把“匹配”與“搜索”拆成兩個遞歸函數(shù)外層HasSubtree負責(zé)在root1上枚舉所有候選根并借助短路求值提前退出內(nèi)層isSubtreeWithRoot負責(zé)在根對齊的前提下逐節(jié)點驗證并用root2 null → true表達“結(jié)構(gòu)已匹配完整”的語義。理解入口空樹防御與驗證過程空樹收尾這兩處空判斷的分工是該題答到面試官點頭的關(guān)鍵再結(jié)合 O(M×N) 最壞時間的復(fù)雜度說明即可完成一次完整而嚴謹?shù)淖鞔??！久赓M下載鏈接】CS-Notes:books: 技術(shù)面試必備基礎(chǔ)知識、Leetcode、計算機操作系統(tǒng)、計算機網(wǎng)絡(luò)、系統(tǒng)設(shè)計項目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考