TNotes.leetcode

Appearance

0104. 二叉树的最大深度【简单】

0104. 二叉树的最大深度【简单】 ​

1. 📝 题目描述 ​

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

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

示例 1：

img

txt
输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

txt
输入：root = [1,null,2]
输出：2

提示：

  • 树中节点的数量在 [0, 10^4] 区间内。
  • -100 <= Node.val <= 100

2. 🎯 s.1 - 递归 ​

js
/**
 * 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, lDep = 0, rDep = 0) {
  if (!root) return Math.max(lDep, rDep)
  lDep = maxDepth(root.left, lDep + 1)
  rDep = maxDepth(root.right, rDep + 1)
  return Math.max(lDep, rDep)
}

3. 🎯 s.2 - 迭代 ​

js
/**
 * 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) {
  if (!root) return 0
  // 使用队列存储每一层的节点
  const queue = [root]
  let depth = 0

  while (queue.length > 0) {
    // 当前层的节点数量
    const levelSize = queue.length
    // 每处理完一层，深度加 1
    depth++

    // 处理当前层的所有节点
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()

      // 将下一层的节点加入队列
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
  }

  // 当队列为空时，返回累计的深度
  return depth
}

Discussions