我偶然发现了一个解决方案，
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
1条答案
按热度按时间jyztefdp1#
这是因为队列长度是动态的，并且不断变化。让我们以你的问题为例。首先，您将在此处的队列中添加3发生了什么：-
在第一次迭代之前
queue = [3], queue.length = 1 and i = 0第一次迭代后，深度应该增加，但看看会发生什么。在循环的第一次迭代之后
queue = [9, 20], queue.length = 2 and i = 1在这里，它应该停止，因为它已经检查了同一级别中的所有值（在本例中是根节点，是3），但它将继续queue.length > i在循环的第二次迭代之后queue = [20], queue.length = 1 and i = 2作为queue.length < i，循环将中断，深度将增加，但在我们将所有子项添加到队列后，深度应增加。这就是它给出错误答案的原因。所以你应该加上queue.length到var所以我们想要做的迭代次数不会改变。