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