使用 BFS 时 N 叉树的最大深度
Maximum Depth of N-ary Tree when use BFS
对于获取二叉树的最大深度,下面的代码是正确答案。
var maxDepth = function(root) {
if (!root) {
return 0
}
let depth = 0;
let arr=[root];
while (arr.length) {
let arrlength=arr.length;
for (let i=0;i<arrlength;i++) {
let curr=arr.shift();
arr.push(...curr.children);
}
depth++;
}
return depth;
};
但是,如果我在 for 循环中使用 arr.length 而不是使用 "let arrlength=arr.length;" 并使用 arrlength,这将是一个错误的答案...
我可以知道为什么吗?我看不出有什么区别。非常感谢!
var maxDepth = function(root) {
if (!root) {
return 0
}
let depth = 0;
let arr=[root];
while (arr.length) {
for (let i=0;i<arr.length;i++) {
let curr=arr.shift();
arr.push(...curr.children);
}
depth++;
}
return depth;
};
可以在这里测试:
https://leetcode.com/problems/maximum-depth-of-n-ary-tree/
let curr = arr.shift()
从数组中删除第一个元素并将其分配给 curr
.
arr.push(...curr.children)
将所有 children 添加到数组末尾。
这两个操作都是改变数组长度,测试i < arr.length
每次通过都使用当前长度。但是循环只应该处理原始数组元素。 arrlength
包含数组在循环之前的原始长度。它不会随着数组的修改而改变,因此循环将运行正确的次数。
如果您在循环之前制作了 arr
的副本,并且循环遍历它而不是修改您循环遍历的数组,则可以在循环中使用 .length
。
var maxDepth = function(root) {
if (!root) {
return 0
}
let depth = 0;
let arr = [root];
while (arr.length) {
let copy = [...arr];
arr.splice(0, arr.length);
for (let i = 0; i < copy.length; i++) {
let curr = copy[i];
arr.push(...curr.children);
}
depth++;
}
return depth;
};
const tree = {
value: 1,
children: [{
value: 3,
children: [{
value: 5,
children: []
}, {
value: 6,
children: []
}]
},
{
value: 2,
children: []
},
{
value: 3,
children: []
}
]
};
console.log(maxDepth(tree));
对于获取二叉树的最大深度,下面的代码是正确答案。
var maxDepth = function(root) {
if (!root) {
return 0
}
let depth = 0;
let arr=[root];
while (arr.length) {
let arrlength=arr.length;
for (let i=0;i<arrlength;i++) {
let curr=arr.shift();
arr.push(...curr.children);
}
depth++;
}
return depth;
};
但是,如果我在 for 循环中使用 arr.length 而不是使用 "let arrlength=arr.length;" 并使用 arrlength,这将是一个错误的答案... 我可以知道为什么吗?我看不出有什么区别。非常感谢!
var maxDepth = function(root) {
if (!root) {
return 0
}
let depth = 0;
let arr=[root];
while (arr.length) {
for (let i=0;i<arr.length;i++) {
let curr=arr.shift();
arr.push(...curr.children);
}
depth++;
}
return depth;
};
可以在这里测试: https://leetcode.com/problems/maximum-depth-of-n-ary-tree/
let curr = arr.shift()
从数组中删除第一个元素并将其分配给 curr
.
arr.push(...curr.children)
将所有 children 添加到数组末尾。
这两个操作都是改变数组长度,测试i < arr.length
每次通过都使用当前长度。但是循环只应该处理原始数组元素。 arrlength
包含数组在循环之前的原始长度。它不会随着数组的修改而改变,因此循环将运行正确的次数。
如果您在循环之前制作了 arr
的副本,并且循环遍历它而不是修改您循环遍历的数组,则可以在循环中使用 .length
。
var maxDepth = function(root) {
if (!root) {
return 0
}
let depth = 0;
let arr = [root];
while (arr.length) {
let copy = [...arr];
arr.splice(0, arr.length);
for (let i = 0; i < copy.length; i++) {
let curr = copy[i];
arr.push(...curr.children);
}
depth++;
}
return depth;
};
const tree = {
value: 1,
children: [{
value: 3,
children: [{
value: 5,
children: []
}, {
value: 6,
children: []
}]
},
{
value: 2,
children: []
},
{
value: 3,
children: []
}
]
};
console.log(maxDepth(tree));