LeetCode 二叉树的最小深度 BFS 题解

题目

二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

解题思路

求最小深度，考虑使用广度优先遍历
在广度优先遍历过程中，遇到叶子节点，停止遍历，返回节点层级
广度优先遍历整棵树，并记录每个节点的层级
遇到叶子节点，返回节点层级，停止遍历

这道题和求最大深度看着像一对，解法思路差别却不小，值得对照理解。

求最大深度必须遍历全部节点，因为最深的路径可能藏在任何分支里。求最小深度不一样：广度优先是按层推进的，第一个遇到的叶子节点必然位于最浅的那一层，此时可以立刻返回，剩下的节点根本不用看。这是广度优先「先访问离根近的节点」这个性质带来的直接收益。

收益有多大取决于树的形状。如果最浅的叶子就在第二层，而整棵树有几万个节点，那么只访问了几个节点就结束了。用深度优先做这道题也能得到正确答案，但它会一头钻到某条分支的底部，没法提前结束，必须把所有分支走完再比较，实际开销大得多。

用深度优先解还有一个额外的坑：不能简单写成左右子树最小深度取较小值加一。因为单侧为空的节点不是叶子节点，比如根节点只有右孩子，左子树的深度是 0，取最小值会得到 1，但正确答案要往右边继续走。必须对「只有一个孩子」的情况单独处理。广度优先的写法天然避开了这个陷阱，因为它判断的是「两个孩子都为空」这个叶子的准确定义。

题解

队列里存的不是单个节点，而是 [节点, 层级] 这样的数组。这是广度优先需要携带额外信息时的常见做法——层级不能像递归那样通过参数往下传，只能跟节点一起放进队列。

var minDepth = function (root) {
  if (!root) return 0;
  const res = 0;
  const q = [[root, 1]];
  while (q) {
    const [n, l] = q.shift();
    if (!n.left && !n.right) return l;
    if (n.left) q.push([n.left, l + 1]);
    if (n.right) q.push([n.right, l + 1]);
  }
};

代码里几个点说明一下。

开头 if (!root) return 0 处理空树，必须放在最前面，否则后面 q.shift() 会拿到 undefined 再解构就报错了。

const [n, l] = q.shift() 用解构直接把节点和层级取出来，比写两次下标访问清楚。初始层级传 1，和最大深度那题一样，根节点自己算一层。

入队前判断 if (n.left)，只把存在的孩子放进队列。这样队列里不会出现空节点，后面判断叶子时就不用再做非空校验了。

循环条件这里写的是 while (q)，需要留意一下：q 是数组，即使是空数组也是真值，所以这个条件永远成立，不会因为队列空了而退出。本题因为二叉树一定存在叶子节点，函数必然从 return l 那里退出，所以能通过。但严格来说应该写成 while (q.length)，靠长度判断队列是否为空——否则一旦输入不符合预期，就会在空队列上解构 undefined 而抛错。另外 const res = 0 这行声明了没被用到，可以删掉。

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

时间上最坏情况要访问所有节点，是 O(n)，但如上所述实际经常远小于此。空间取决于队列中同时存在的最大节点数，也就是树最宽那一层，最坏是 O(n)。

另外 q.shift() 是 O(n) 操作，节点很多时会成为瓶颈，可以改成用一个下标指针代替 shift，出队变成 O(1)。