題目描述：輸入一棵二叉樹的根節(jié)點(diǎn)死遭，求該樹的深度。從根節(jié)點(diǎn)到葉節(jié)點(diǎn)依次經(jīng)過的節(jié)點(diǎn)（含根凯旋、葉節(jié)點(diǎn)）形成樹的一條路徑，最長(zhǎng)路徑的長(zhǎng)度為樹的深度至非。
解法 1: 遞歸
遞歸的寫法非常直觀钠署。對(duì)于一棵二叉樹來說，它的高度等于左右子樹的高度最大值荒椭，加上 1谐鼎。
代碼實(shí)現(xiàn)如下：
// ac地址：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
// 原文地址：https://xxoo521.com/2020-03-22-max-depth/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
if (!root) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};
解法 2: 層序遍歷
按照二叉樹的“層”去遍歷，最后返回層的數(shù)目趣惠。這題和《劍指 offer - 從上到下打印二叉樹 III - JavaScript》思路完全一樣狸棍。
細(xì)節(jié)請(qǐng)看代碼注釋，代碼實(shí)現(xiàn)如下：
// ac地址：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
// 原文地址：https://xxoo521.com/2020-03-22-max-depth/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
if (!root) return 0;
let res = 0;
const queue = [root];
while (queue.length) {
let levelNum = queue.length; // 當(dāng)前層中二叉樹的節(jié)點(diǎn)數(shù)量
++res;
// 依次將下一層的二叉樹節(jié)點(diǎn)放入隊(duì)列
while (levelNum--) {
const node = queue.shift();
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
return res;
};
更多資料
整理不易味悄，若對(duì)您有幫助草戈，請(qǐng)給個(gè)「關(guān)注+點(diǎn)贊」，您的支持是我更新的動(dòng)力 ??
- ??Blog：劍指 Offer 題解 + JS 代碼
- ??Github ：https://github.com/dongyuanxin/blog
- ?? 公眾號(hào)：心譚博客
