111. 二叉树的最小深度 🟩

题目

LeetCode 简单

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

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

方法：广度优先

BFS 队列

时间复杂度：O(n)
空间复杂度：O(height)

❓ 为什么最小深度极其不推荐用 DFS（栈）？
✅ 想象一棵树，它的左子树有 10000 层深，而右子树只有 2 层深。

// 1. 定义二叉树节点
class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

function minDepth(root) {
  if (root === null) return 0

  // 队列里存放的是 [当前节点, 当前节点的深度]
  const queue = [[root, 1]]

  while (queue.length > 0) {
    console.log(
      'queue',
      JSON.stringify(queue.map(([node, depth]) => [node.val, depth])),
    )

    // 从队列头部取出一个节点 (BFS 层序遍历)
    const [node, depth] = queue.shift()

    // 🚨 终极核武器：一旦遇到第一个“叶子节点”，直接返回当前的深度！
    // 因为是层序遍历，最先遇到的叶子一定是距离根节点最近的！
    if (node.left === null && node.right === null) {
      return depth
    }

    // 如果不是叶子节点，就把它的孩子和“深度+1”推入队列尾部
    if (node.left) {
      queue.push([node.left, depth + 1])
    }
    if (node.right) {
      queue.push([node.right, depth + 1])
    }
  }
}

//       3
//      / \
//     9   20
//         / \
//        15  7
const treeA = new TreeNode(3)
treeA.left = new TreeNode(9)
treeA.right = new TreeNode(20, new TreeNode(15), new TreeNode(7))

console.log('🌰', JSON.stringify(minDepth(treeA))) // 2

执行结果

queue [[3,1]]
queue [[9,2],[20,2]]
🌰 2

本页目录

题目

方法：广度优先