二叉树的最小深度：BFS，Javascript (leetcode 111)

Question

我偶然发现了一个解决方案，

var minDepth = function(root) {
if(!root) return 0;
let depth = 1;
let queue = [root];
if(!root.left && !root.right) return depth;

while(queue.length > 0 ){
  let queueLength = queue.length;

  for(let i = 0; i < queueLength; i++){
    let node = queue.shift();

    if(!node.left && !node.right) return depth;
    else{
      if(node.left) queue.push(node.left);
      if(node.right) queue.push(node.right);
    }
  }

  depth++;
}

return depth;
};

此代码在未将队列长度分配给变量的情况下给出错误答案。

let queueLength = queue.length;

  for(let i = 0; i < queueLength; i++) ...

这是怎么回事？

示例：输入 - [3, 9, 20, null, null, 15, 7]

输出：使用变量 - 2（右）

没有 var - 1

Answer 1

这是因为队列的长度是动态的，不断变化的。让我们以你的问题为例。首先，您将在此处添加 3 个队列会发生什么：-

在第一次迭代之前 queue = [3], queue.length = 1 and i = 0

深度应该在第一次迭代后增加，但看看会发生什么。

循环第一次迭代后 queue = [9, 20], queue.length = 2 and i = 1

在这里它应该停止，因为它已经检查了同一级别的所有值（在本例中是根节点，即 3）但它继续为 queue.length > i

在循环的第 2 次迭代后 queue = [20], queue.length = 1 and i = 2

as queue.length < i，循环会中断，深度会增加，但在我们将所有子项添加到队列后深度应该会增加，这就是它给出错误答案的原因。所以你应该添加 queue.length 到 var 这样我们想要做的迭代次数就不会改变。

二叉树的最小深度：BFS，Javascript (leetcode 111)

Minimum depth of binary tree : BFS , Javascript (leetcode 111)

javascript

binary-tree

breadth-first-search

data-structures