教程【免費下載鏈接】InterviewGuide「InterviewGuide」是阿秀從校園-職場多年計算機自學(xué)過程的記錄以及學(xué)弟學(xué)妹們計算機校招秋招經(jīng)驗總結(jié)文章的匯總包括但不限于C/C 、Golang、JavaScript、Vue、操作系統(tǒng)、數(shù)據(jù)結(jié)構(gòu)、計算機網(wǎng)絡(luò)、MySQL、Redis等學(xué)習(xí)總結(jié)堅持學(xué)習(xí)持續(xù)成長項目地址https://gitcode.com/gh_mirrors/in/InterviewGuide點擊查看免費下載本篇是阿秀《InterviewGuide》精選力扣刷題筆記中深度優(yōu)先搜索DFS分類下的經(jīng)典二叉樹題目解析。題目同時出現(xiàn)在《劍指 Offer》第 38 題二叉樹深度與力扣主站 104 題二叉樹的最大深度中是校招、社招筆試面試中出現(xiàn)頻率極高的入門級 DFS 題目。讀完本篇你將掌握求二叉樹深度的遞歸后序遍歷 DFS與迭代層序 BFS兩種標準解法理解各自的復(fù)雜度特征與適用場景并能將其遷移到最小深度、平衡二叉樹等衍生題目上。一、題目描述輸入一棵二叉樹的根節(jié)點求該樹的深度。從根節(jié)點到葉節(jié)點依次經(jīng)過的節(jié)點含根、葉節(jié)點形成樹的一條路徑最長路徑的長度即為樹的深度。示例給定二叉樹[3,9,20,null,null,15,7]3 / \ 9 20 / \ 15 7返回它的最大深度3。提示節(jié)點總數(shù) 10000注意本題與力扣主站104 題二叉樹的最大深度完全相同只是題目編號與出處不同。倉庫中該題的原始筆記位于 面試題55-I.二叉樹的深度同題的另一個版本筆記為 104.二叉樹的最大深度兩者可對照閱讀。二、思路一后序遍歷式 DFS 遞歸原題官方解法這是原文檔給出的解法。一棵樹的深度可以遞歸地定義樹為空時深度為 0否則深度 1 max(左子樹深度, 右子樹深度)。遞歸天然對應(yīng)二叉樹的自底向上后序遍歷——先求左右子樹的深度再在當(dāng)前節(jié)點匯總。class Solution { public: int maxDepth(TreeNode* root) { if (!root ) return 0; if (root-left root-right) return 1max(maxDepth(root-right),maxDepth(root-left)); if (!root-left) return 1 maxDepth(root-right); else return 1maxDepth(root-left); } };逐行拆解代碼分支語義if (!root) return 0;遞歸出口空節(jié)點葉子的 NULL 孩子深度為 0if (root-left root-right)左右孩子都存在取兩側(cè)遞歸結(jié)果較大者 1if (!root-left)只有右孩子或走到葉子時!root-left成立、root-right為 NULL直接下沉到右子樹else return 1 maxDepth(root-left);只有左孩子直接下沉到左子樹作者當(dāng)時的提交記錄為執(zhí)行用時 4 ms擊敗 99.36% 的 C 提交內(nèi)存消耗 20.8 MB擊敗 100.00% 的用戶。需要說明的是LeetCode 的運行用時與內(nèi)存會隨提交環(huán)境、測試集規(guī)模波動同一段代碼在倉庫 104.二叉樹的最大深度 中記錄的提交結(jié)果為 20 ms / 19.82%因此這些百分比只代表當(dāng)時單次提交的快照不必過度解讀重點在于理解算法本身的復(fù)雜度。三、思路二統(tǒng)一模板的遞歸變種更簡潔上面第一版解法把左右孩子是否存在拆成了多個分支判斷。其實可以合并成一條更通用的遞歸式——先分別求左右子樹深度再加 1 取最大值空節(jié)點天然返回 0無需單獨討論只有單孩子的情況int maxDepth(TreeNode* root) { if (!root ) return 0; int left_depth maxDepth(root-left) 1, right_depth maxDepth(root-right) 1; return max(left_depth,right_depth); }這個寫法與《劍指 Offer》No38 中給出的二刷版本在邏輯上完全等價倉庫見 38-劍指offer.mdint TreeDepth(TreeNode* pRoot) { if(pRoot nullptr) return 0; int leftDepth TreeDepth(pRoot-left); int rightDepth TreeDepth(pRoot-right); return 1 max(leftDepth,rightDepth); }兩種寫法的差異只在于1是加在遞歸返回值上還是加在局部變量上都屬于后序遍歷的 DFS。從可讀性與面試手寫速度來看統(tǒng)一模板更推薦因為它把深度遞推公式表達得最直白。復(fù)雜度分析兩種遞歸寫法一致時間復(fù)雜度O(n)每個節(jié)點恰好被訪問一次空間復(fù)雜度最壞情況O(n)——當(dāng)二叉樹退化為單鏈如每個節(jié)點只有左孩子時遞歸棧深度等于節(jié)點數(shù)平均/最好情況平衡樹下為O(log n)。四、思路三BFS 層序遍歷迭代版可防止爆棧遞歸在極端深鏈上可能棧溢出改用顯式隊列做層序遍歷則完全不依賴系統(tǒng)調(diào)用棧。原文檔雖只給了遞歸寫法但倉庫同題筆記 104.二叉樹的最大深度 與 38-劍指offer.md 都補充了 BFS 版本這里一并收入int maxDepth(TreeNode* root) { if (!root) return 0; int max_dept 0; queuepairTreeNode*, int q; q.push({ root,1 }); // 根節(jié)點深度記為 1 while (!q.empty()) { TreeNode* curr_node q.front().first; int curr_dept q.front().second; q.pop(); if (curr_node) { max_dept max(max_dept, curr_dept); // 每彈出一個節(jié)點就刷新最大深度 q.push({ curr_node-left, curr_dept 1 }); q.push({ curr_node-right, curr_dept 1 }); } } return max_dept; }BFS 版的關(guān)鍵點隊列元素是pairTreeNode*, int第二個字段記錄該節(jié)點所在深度入隊時深度加 1空節(jié)點也照常入隊但在出隊時用if (curr_node)跳過因此不需要在入隊前判空邏輯更統(tǒng)一由于是逐層推進隊內(nèi)節(jié)點的深度單調(diào)遞增所以max_dept也可以等價為最后一個出隊節(jié)點的深度但用max維護更直觀、更穩(wěn)健。復(fù)雜度時間O(n)空間O(w)w為隊列最大寬度平衡二叉樹時約為O(n/2)量級。它的最大優(yōu)勢是把遞歸調(diào)用棧換成了堆上的隊列在處理深度高達 10000 的單鏈樹時不會爆棧。五、兩種思路對比小結(jié)維度DFS 遞歸后序BFS 迭代層序核心思想深度 1 max(左右子樹深度)逐層向下記錄層號最大值時間復(fù)雜度O(n)O(n)空間復(fù)雜度最壞 O(n)鏈式樹遞歸棧O(w)隊列寬度最壞約 n/2代碼量3~5 行最簡潔約 10 行稍長風(fēng)險點深鏈可能棧溢出無遞歸棧風(fēng)險適用場景面試手寫首選、代碼量小生產(chǎn)環(huán)境 / 深樹 / 防止爆棧對于本題節(jié)點總數(shù) 10000的限制兩種寫法在力扣環(huán)境下都能順利通過但面試官常會追問如果樹很深怎么辦此時能答出 BFS 迭代方案會是明顯的加分項。六、舉一反三從最大深度到同族題目二叉樹深度問題是一個小家族倉庫的 DFS 分類目錄見 13-DFS 目錄中還收錄了以下幾道同族題目解法可以互相遷移1. 最小深度力扣 111——見 111.二叉樹的最小深度。注意不能簡單把max換成min因為最小深度要求到最近葉子節(jié)點單孩子節(jié)點必須繼續(xù)下沉int minDepth(TreeNode* root) { if (!root) return 0; if (!root-left !root-right) return 1; else if (!root-left root-right) return 1 minDepth(root-right); else if (!root-right root-left ) return 1 minDepth(root-left); return min(minDepth(root-left), minDepth(root-right)) 1; }2. 平衡二叉樹劍指 Offer 55-II / No39——見 39-劍指offer.md。直接復(fù)用深度計算函數(shù)每個節(jié)點左右子樹高度差不超過 1 即為平衡樹。暴力寫法是先求深度再判斷會重復(fù)遍歷改進寫法是從下往上返回高度、發(fā)現(xiàn)不平衡立即返回 -1 剪枝int getDepth(TreeNode* node) { if (node nullptr) return 0; int leftDept getDepth(node-left); if (leftDept -1) return -1; int rightDept getDepth(node-right); if (rightDept -1) return -1; if (abs(leftDept - rightDept) 1) return -1; else return 1 max(leftDept, rightDept); } bool IsBalanced_Solution(TreeNode* pRoot) { if (pRoot nullptr) return true; return getDepth(pRoot) ! -1; }3. 最小高度樹面試題 04.02——見 面試題04.02.最小高度樹。這是深度的逆問題給定升序數(shù)組構(gòu)造高度最小的二叉搜索樹利用二分法取中點為根、遞歸構(gòu)造左右子樹即可每個節(jié)點深度貢獻 1整棵樹高度天然最小。七、本篇小結(jié)面試題55-I 力扣 104是二叉樹類題目的地基題遞歸模板1 max(left, right)要能閉著眼睛寫出來并講清楚后序遍歷的含義BFS 層序迭代版要會寫、知道它能防爆棧作為深樹場景的備選方案掌握深度這一基本量后最小深度、平衡二叉樹判斷等衍生題都可以建立在其上這是面試官最常做的由淺入深追問路線。倉庫中同族題目的完整筆記可繼續(xù)對照閱讀104.二叉樹的最大深度、111.二叉樹的最小深度、劍指 Offer No38 二叉樹深度、劍指 Offer No39 平衡二叉樹以及 DFS 分類目錄 中其余題目。贊分享教程【免費下載鏈接】InterviewGuide「InterviewGuide」是阿秀從校園-職場多年計算機自學(xué)過程的記錄以及學(xué)弟學(xué)妹們計算機校招秋招經(jīng)驗總結(jié)文章的匯總包括但不限于C/C 、Golang、JavaScript、Vue、操作系統(tǒng)、數(shù)據(jù)結(jié)構(gòu)、計算機網(wǎng)絡(luò)、MySQL、Redis等學(xué)習(xí)總結(jié)堅持學(xué)習(xí)持續(xù)成長項目地址https://gitcode.com/gh_mirrors/in/InterviewGuide點擊查看免費下載相關(guān)推薦劍指Offer No38 二叉樹的深度遞歸DFS與BFS迭代全解法剖析InterviewGuide 刷題筆記劍指Offer No38 二叉樹的深度遞歸DFS與BFS迭代全解法剖析InterviewGuide 刷題筆記 本文是 InterviewGuide 倉庫「文檔教程知識庫面試題55-I. 二叉樹的深度DFS 遞歸與 BFS 迭代兩種解法詳解InterviewGuide 力扣刷題筆記面試題55 I. 二叉樹的深度DFS 遞歸與 BFS 迭代兩種解法詳解InterviewGuide 力扣刷題筆記 本文是 InterviewGuide 項文檔教程知識庫LeetCode 104. 二叉樹的最大深度InterviewGuide 精選 DFS 刷題筆記C 遞歸與 BFS 全解LeetCode 104. 二叉樹的最大深度InterviewGuide 精選 DFS 刷題筆記C 遞歸與 BFS 全解 本篇是 InterviewG教程上一篇如何零配置實現(xiàn)Jazzy文檔自動化測試保障API文檔一致性的完整方案下一篇librealsense RealSense 深度相機 SDK 部署調(diào)優(yōu)實戰(zhàn)手冊從首幀到生產(chǎn)級創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考 InterviewGuide 劍指 Offer 面試題55-I：二叉樹的深度（LeetCode 104）——DFS 遞歸與 BFS 迭代全解
教程【免費下載鏈接】InterviewGuide「InterviewGuide」是阿秀從校園-職場多年計算機自學(xué)過程的記錄以及學(xué)弟學(xué)妹們計算機校招秋招經(jīng)驗總結(jié)文章的匯總包括但不限于C/C 、Golang、JavaScript、Vue、操作系統(tǒng)、數(shù)據(jù)結(jié)構(gòu)、計算機網(wǎng)絡(luò)、MySQL、Redis等學(xué)習(xí)總結(jié)堅持學(xué)習(xí)持續(xù)成長項目地址https://gitcode.com/gh_mirrors/in/InterviewGuide點擊查看免費下載本篇是阿秀《InterviewGuide》精選力扣刷題筆記中深度優(yōu)先搜索DFS分類下的經(jīng)典二叉樹題目解析。題目同時出現(xiàn)在《劍指 Offer》第 38 題二叉樹深度與力扣主站 104 題二叉樹的最大深度中是校招、社招筆試面試中出現(xiàn)頻率極高的入門級 DFS 題目。讀完本篇你將掌握求二叉樹深度的遞歸后序遍歷 DFS與迭代層序 BFS兩種標準解法理解各自的復(fù)雜度特征與適用場景并能將其遷移到最小深度、平衡二叉樹等衍生題目上。一、題目描述輸入一棵二叉樹的根節(jié)點求該樹的深度。從根節(jié)點到葉節(jié)點依次經(jīng)過的節(jié)點含根、葉節(jié)點形成樹的一條路徑最長路徑的長度即為樹的深度。示例給定二叉樹[3,9,20,null,null,15,7]3 / \ 9 20 / \ 15 7返回它的最大深度3。提示節(jié)點總數(shù) 10000注意本題與力扣主站104 題二叉樹的最大深度完全相同只是題目編號與出處不同。倉庫中該題的原始筆記位于 面試題55-I.二叉樹的深度同題的另一個版本筆記為 104.二叉樹的最大深度兩者可對照閱讀。二、思路一后序遍歷式 DFS 遞歸原題官方解法這是原文檔給出的解法。一棵樹的深度可以遞歸地定義樹為空時深度為 0否則深度 1 max(左子樹深度, 右子樹深度)。遞歸天然對應(yīng)二叉樹的自底向上后序遍歷——先求左右子樹的深度再在當(dāng)前節(jié)點匯總。class Solution { public: int maxDepth(TreeNode* root) { if (!root ) return 0; if (root-left root-right) return 1max(maxDepth(root-right),maxDepth(root-left)); if (!root-left) return 1 maxDepth(root-right); else return 1maxDepth(root-left); } };逐行拆解代碼分支語義if (!root) return 0;遞歸出口空節(jié)點葉子的 NULL 孩子深度為 0if (root-left root-right)左右孩子都存在取兩側(cè)遞歸結(jié)果較大者 1if (!root-left)只有右孩子或走到葉子時!root-left成立、root-right為 NULL直接下沉到右子樹else return 1 maxDepth(root-left);只有左孩子直接下沉到左子樹作者當(dāng)時的提交記錄為執(zhí)行用時 4 ms擊敗 99.36% 的 C 提交內(nèi)存消耗 20.8 MB擊敗 100.00% 的用戶。需要說明的是LeetCode 的運行用時與內(nèi)存會隨提交環(huán)境、測試集規(guī)模波動同一段代碼在倉庫 104.二叉樹的最大深度 中記錄的提交結(jié)果為 20 ms / 19.82%因此這些百分比只代表當(dāng)時單次提交的快照不必過度解讀重點在于理解算法本身的復(fù)雜度。三、思路二統(tǒng)一模板的遞歸變種更簡潔上面第一版解法把左右孩子是否存在拆成了多個分支判斷。其實可以合并成一條更通用的遞歸式——先分別求左右子樹深度再加 1 取最大值空節(jié)點天然返回 0無需單獨討論只有單孩子的情況int maxDepth(TreeNode* root) { if (!root ) return 0; int left_depth maxDepth(root-left) 1, right_depth maxDepth(root-right) 1; return max(left_depth,right_depth); }這個寫法與《劍指 Offer》No38 中給出的二刷版本在邏輯上完全等價倉庫見 38-劍指offer.mdint TreeDepth(TreeNode* pRoot) { if(pRoot nullptr) return 0; int leftDepth TreeDepth(pRoot-left); int rightDepth TreeDepth(pRoot-right); return 1 max(leftDepth,rightDepth); }兩種寫法的差異只在于1是加在遞歸返回值上還是加在局部變量上都屬于后序遍歷的 DFS。從可讀性與面試手寫速度來看統(tǒng)一模板更推薦因為它把深度遞推公式表達得最直白。復(fù)雜度分析兩種遞歸寫法一致時間復(fù)雜度O(n)每個節(jié)點恰好被訪問一次空間復(fù)雜度最壞情況O(n)——當(dāng)二叉樹退化為單鏈如每個節(jié)點只有左孩子時遞歸棧深度等于節(jié)點數(shù)平均/最好情況平衡樹下為O(log n)。四、思路三BFS 層序遍歷迭代版可防止爆棧遞歸在極端深鏈上可能棧溢出改用顯式隊列做層序遍歷則完全不依賴系統(tǒng)調(diào)用棧。原文檔雖只給了遞歸寫法但倉庫同題筆記 104.二叉樹的最大深度 與 38-劍指offer.md 都補充了 BFS 版本這里一并收入int maxDepth(TreeNode* root) { if (!root) return 0; int max_dept 0; queuepairTreeNode*, int q; q.push({ root,1 }); // 根節(jié)點深度記為 1 while (!q.empty()) { TreeNode* curr_node q.front().first; int curr_dept q.front().second; q.pop(); if (curr_node) { max_dept max(max_dept, curr_dept); // 每彈出一個節(jié)點就刷新最大深度 q.push({ curr_node-left, curr_dept 1 }); q.push({ curr_node-right, curr_dept 1 }); } } return max_dept; }BFS 版的關(guān)鍵點隊列元素是pairTreeNode*, int第二個字段記錄該節(jié)點所在深度入隊時深度加 1空節(jié)點也照常入隊但在出隊時用if (curr_node)跳過因此不需要在入隊前判空邏輯更統(tǒng)一由于是逐層推進隊內(nèi)節(jié)點的深度單調(diào)遞增所以max_dept也可以等價為最后一個出隊節(jié)點的深度但用max維護更直觀、更穩(wěn)健。復(fù)雜度時間O(n)空間O(w)w為隊列最大寬度平衡二叉樹時約為O(n/2)量級。它的最大優(yōu)勢是把遞歸調(diào)用棧換成了堆上的隊列在處理深度高達 10000 的單鏈樹時不會爆棧。五、兩種思路對比小結(jié)維度DFS 遞歸后序BFS 迭代層序核心思想深度 1 max(左右子樹深度)逐層向下記錄層號最大值時間復(fù)雜度O(n)O(n)空間復(fù)雜度最壞 O(n)鏈式樹遞歸棧O(w)隊列寬度最壞約 n/2代碼量3~5 行最簡潔約 10 行稍長風(fēng)險點深鏈可能棧溢出無遞歸棧風(fēng)險適用場景面試手寫首選、代碼量小生產(chǎn)環(huán)境 / 深樹 / 防止爆棧對于本題節(jié)點總數(shù) 10000的限制兩種寫法在力扣環(huán)境下都能順利通過但面試官常會追問如果樹很深怎么辦此時能答出 BFS 迭代方案會是明顯的加分項。六、舉一反三從最大深度到同族題目二叉樹深度問題是一個小家族倉庫的 DFS 分類目錄見 13-DFS 目錄中還收錄了以下幾道同族題目解法可以互相遷移1. 最小深度力扣 111——見 111.二叉樹的最小深度。注意不能簡單把max換成min因為最小深度要求到最近葉子節(jié)點單孩子節(jié)點必須繼續(xù)下沉int minDepth(TreeNode* root) { if (!root) return 0; if (!root-left !root-right) return 1; else if (!root-left root-right) return 1 minDepth(root-right); else if (!root-right root-left ) return 1 minDepth(root-left); return min(minDepth(root-left), minDepth(root-right)) 1; }2. 平衡二叉樹劍指 Offer 55-II / No39——見 39-劍指offer.md。直接復(fù)用深度計算函數(shù)每個節(jié)點左右子樹高度差不超過 1 即為平衡樹。暴力寫法是先求深度再判斷會重復(fù)遍歷改進寫法是從下往上返回高度、發(fā)現(xiàn)不平衡立即返回 -1 剪枝int getDepth(TreeNode* node) { if (node nullptr) return 0; int leftDept getDepth(node-left); if (leftDept -1) return -1; int rightDept getDepth(node-right); if (rightDept -1) return -1; if (abs(leftDept - rightDept) 1) return -1; else return 1 max(leftDept, rightDept); } bool IsBalanced_Solution(TreeNode* pRoot) { if (pRoot nullptr) return true; return getDepth(pRoot) ! -1; }3. 最小高度樹面試題 04.02——見 面試題04.02.最小高度樹。這是深度的逆問題給定升序數(shù)組構(gòu)造高度最小的二叉搜索樹利用二分法取中點為根、遞歸構(gòu)造左右子樹即可每個節(jié)點深度貢獻 1整棵樹高度天然最小。七、本篇小結(jié)面試題55-I 力扣 104是二叉樹類題目的地基題遞歸模板1 max(left, right)要能閉著眼睛寫出來并講清楚后序遍歷的含義BFS 層序迭代版要會寫、知道它能防爆棧作為深樹場景的備選方案掌握深度這一基本量后最小深度、平衡二叉樹判斷等衍生題都可以建立在其上這是面試官最常做的由淺入深追問路線。倉庫中同族題目的完整筆記可繼續(xù)對照閱讀104.二叉樹的最大深度、111.二叉樹的最小深度、劍指 Offer No38 二叉樹深度、劍指 Offer No39 平衡二叉樹以及 DFS 分類目錄 中其余題目。贊分享教程【免費下載鏈接】InterviewGuide「InterviewGuide」是阿秀從校園-職場多年計算機自學(xué)過程的記錄以及學(xué)弟學(xué)妹們計算機校招秋招經(jīng)驗總結(jié)文章的匯總包括但不限于C/C 、Golang、JavaScript、Vue、操作系統(tǒng)、數(shù)據(jù)結(jié)構(gòu)、計算機網(wǎng)絡(luò)、MySQL、Redis等學(xué)習(xí)總結(jié)堅持學(xué)習(xí)持續(xù)成長項目地址https://gitcode.com/gh_mirrors/in/InterviewGuide點擊查看免費下載相關(guān)推薦劍指Offer No38 二叉樹的深度遞歸DFS與BFS迭代全解法剖析InterviewGuide 刷題筆記劍指Offer No38 二叉樹的深度遞歸DFS與BFS迭代全解法剖析InterviewGuide 刷題筆記 本文是 InterviewGuide 倉庫「文檔教程知識庫面試題55-I. 二叉樹的深度DFS 遞歸與 BFS 迭代兩種解法詳解InterviewGuide 力扣刷題筆記面試題55 I. 二叉樹的深度DFS 遞歸與 BFS 迭代兩種解法詳解InterviewGuide 力扣刷題筆記 本文是 InterviewGuide 項文檔教程知識庫LeetCode 104. 二叉樹的最大深度InterviewGuide 精選 DFS 刷題筆記C 遞歸與 BFS 全解LeetCode 104. 二叉樹的最大深度InterviewGuide 精選 DFS 刷題筆記C 遞歸與 BFS 全解 本篇是 InterviewG教程上一篇如何零配置實現(xiàn)Jazzy文檔自動化測試保障API文檔一致性的完整方案下一篇librealsense RealSense 深度相機 SDK 部署調(diào)優(yōu)實戰(zhàn)手冊從首幀到生產(chǎn)級創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考