【每天学习一点算法2025/12/16】二叉树的最大深度

每天学习一点算法 2025/12/16

题目：二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

要取得二叉树的最大深度，就需要遍历树，二叉树的遍历方法我的另一篇前端算法基础的文章中有介绍，主要就是深度优先和广度优先两种算法。

1. 深度优先 — 使用递归的方式遍历二叉树

   计算最大深度，关键在于我们要如何找到深度最大的路径，我们知道深度优先分为前序中序后序，区别就在于处理当前遍历值和左右树叉递归调用的顺序，下面是前序遍历的算法，我们来分析一下

   constpreOrderDFS=(root)=>{if(!root)returnresult.push(root.val)preOrderDFS(root.left)preOrderDFS(root.right)returnresult}

   • 我们主要分析递归遍历的过程，当!root为true时，代表当前路径走到了叶子节点。先序遍历是左节点回归后再进入右节点。
   • 如果我们从叶子节点开始计数，每回归一层+1，然后将数字返回到上一层，这样是不是就可以计算出路径的深度了。
   • 那我们要如何保证计数的是最大深度的路径上的节点呢？只需要每一层取左右节点回归计数值较大的+1返回上一层即可。有点抽象啊，我们简单的举个例子：
     1. 当我们遍历到某一条路径的叶子节点时，返回0到上一层。
     2. 到这个叶子节点这一层时，没有子节点，左右回归计数都是0，返回0+1到上一层。
     3. 到这个叶子节点的父节点这层时，这一侧（可能是left也可能是right）的计数是1，另一侧的计数则要看其子节点的层数情况，哪一侧子层级更深计数就更大，然后就在这基础上+1返回到上一层。
     4. 依次类推每一层都选择计数更大的一侧+1回归，直到回到根节点。

   代码如下：

   functionmaxDepth(root:TreeNode|null):number{if(!root){return0}returnMath.max(maxDepth(root.left),maxDepth(root.right))+1};

2. 广度优先 — 从根节点开始一层一层的遍历，主要利用队列存储下一列节点的方式，具体实现可以参考我的文章前端算法基础，每次遍历其实就是往下一层拓展，那么拓展的次数就是二叉树的最大深度。

   functionmaxDepth(root:TreeNode|null):number{if(!root)return0;constqueue=[root]// 初始根入遍历队列letcount=0// 用于拓展计数// 循环至遍历队列为空while(queue.length){constlevelSize=queue.length;for(leti=0;i<levelSize;i++){constnode=queue.shift()// 第一项出遍历队列// 按左右顺序 将下一层树节点入遍历队列node.left&&queue.push(node.left)node.right&&queue.push(node.right)}// 每层遍历后计数count++}returncount};

题目来源：力扣（LeetCode）