使用 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) 将所有 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));

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

Maximum Depth of N-ary Tree when use BFS

javascript

algorithm

data-structures

tree

breadth-first-search