LeetCode 「简单」104.二叉树的最大深度
题目描述
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例
输入：root = [3,9,20,null,null,15,7]
输出：3
输入：root = [1,null,2]
输出：2
解答
迭代（广度优先搜索，BFS）
关键思路
- 定义问题
- 二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数
- 迭代逻辑
- 使用队列逐层访问树的所有节点
- 每访问完一层，深度加 1
- 迭代终止条件
- 当队列为空时，所有节点都已访问完毕
具体步骤
- 初始化队列
- 将根节点加入队列
- 迭代逻辑
- 使用
while循环，条件是队列不为空 - 在每次循环中，记录当前层的节点数量，然后逐个从队列中取出节点，如果节点有左子节点或右子节点，将其加入队列
- 计算深度
- 每次完成一层的访问之后，深度加 1
- 返回结果
- 当队列为空时，返回计算得到的深度
Code
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
// 如果根节点为空，直接返回深度为 0
if (!root) return 0;
// 使用队列存储待访问的节点
const queue = [root];
// 用于记录当前深度
let depth = 0;
while (queue.length) {
// 当前层的节点数量
const currentSize = queue.length;
while (currentSize-- > 0) {
// 从队列中取出一个节点
const node = queue.shift();
// 如果有左子节点，加入队列
if (node.left) queue.push(node.left);
// 如果有右子节点，加入队列
if (node.right) queue.push(node.right);
}
// 每访问完一层，深度加 1
++depth;
}
return depth;
};