javascript - 使用 BFS 时 N 叉树的最大深度

Question

对于获取二叉树的最大深度，下面的代码是正确答案。

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/

Answer 1

let curr = arr.shift()从数组中删除第一个元素并将其分配给 curr .

arr.push(...curr.children)将所有 child 添加到数组的末尾。

这两个操作都会改变数组长度，而测试i < arr.length每次使用当前长度。但是循环只应该处理原始数组元素。 arrlength包含数组在循环之前的原始长度。它不会随着数组的修改而改变，因此循环将运行正确的次数。

你可以使用 .length如果您复制了 arr，则在循环中在循环之前，并遍历它而不是修改你正在循环的数组。

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));