阿竺 ·1. 前言
二叉樹算法題也是面試中常見的一類題目，相對于鏈表，二叉樹每個節點存在兩個指針，結構更為復雜。但是相對于節點中有多個指針的多叉樹，雙節點的操作相對簡潔，所以比較適合在面試中的白板編程。二叉樹有一些經典問題，例如判斷一顆二叉樹是否屬于平衡二叉樹，將一顆二叉樹展開為單鏈表，求解二叉樹的深度，二叉樹的前序、中序、后序遍歷等。這些題目存在基本的算法模板，本章將探討求解二叉樹深度題目。
2. 二叉樹深度
面試官提問：給定一個二叉樹根節點，如何求解這棵二叉樹最大深度？
題目解析：
求解二叉樹深度問題是來源于算法網站LeetCode的經典題目，題目鏈接：https://leetcode.com/problems/maximum-depth-of-binary-tree/。
首先給出二叉樹最大深度的定義：二叉樹從根節點到所有葉子節點的最長一條路徑。例如下圖的二叉樹，最大深度路徑就是3 -> 20 -> 16以及3 -> 20 -> 8，所以最大深度為2。
求解二叉樹問題的通用解法是遞歸算法，使用遞歸需要滿足三個條件：
（1）初始問題可以拆分為多個子問題；
（2）子問題除了數據量不同，求解思路和初始問題相同；
（3）必須存在遞歸終止條件。
遞歸算法的優勢是代碼簡潔，在面試過程中白板編程能容易實現 bug free，所以比較推薦候選人盡量采用遞歸。
二叉樹自身的數據結構也可以通過遞歸實現，對于根節點以及任何一個中間節點，本質上都是存在兩個左右子樹指針（葉子節點的子樹存在，但為空）。
回到題目，對于任何一個節點，如果我們知道左右子樹的深度，那么左右子樹深度的最大值加一，就是當前節點的深度，這就是子問題的通用解法。最后，確定遞歸終止條件：如果我們遍歷到了空節點，那么停止搜索，算法的 Java 實現，示例：
class Solution {
public int maxDepth(TreeNode root) {
//主函數入口
int depth=0;
depth=calDepth(root, depth);
return depth;
}
public int calDepth(TreeNode node, int depth){
//遞歸終止條件：如果到了空節點，直接返回深度
if(node==null)
return depth;
//深度+1
depth++;
//返回左右子樹的最大深度
return Math.max(calDepth(node.left, depth), calDepth(node.right,depth));
}
}
從本題中我們可以抽象得到二叉樹問題的常見通用解決方案。
二叉樹遞歸本質上屬于深度優先搜索算法，我們定義深度優先搜索的 DFS函數，在 DFS 中首先要給出遞歸終止條件，常見的終止條件是二叉樹的葉子節點或者空節點，其次是對于函數入參根節點的左子樹和右子樹調用函數，在不同函數之間定義 counter 記錄結果值或者中間變量值。
算法的偽代碼，示例：
public void Solution(TreeNode root){
//調用遞歸函數
dfs(root,counter);
}
public Object dfs(TreeNode root, Object counter){
//1. 遞歸終止判斷
if(...)
...
//2. 遞歸調用
dfs(root.left, counter_1);
dfs(root.right, counter_2);
...
}
3. 小結
本章節中我們給出了二叉樹最大深度的算法解法，候選人在編寫代碼時需要注意邊界條件，完成之后可以通過少數幾個節點的簡單二叉樹驗證算法運行是否符合預期。最后，我們給出了二叉樹搜索的通用遞歸解法，對于相似的題目，例如求解二叉樹的高度，判斷一顆二叉樹是否屬于平衡二叉樹，都可以使用遞歸。
2025 imooc.com All Rights Reserved |