Максимальная глубина N-арного дерева при использовании BFS - PullRequest
Новая
       31

Максимальная глубина N-арного дерева при использовании BFS

0 голосов
/ 26 января 2019

Чтобы получить максимальную глубину дерева, этот код ниже является правильным ответом. 

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;

};

Однако, если я использую arr.length в цикле for вместо использования "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/

1 Ответ

0 голосов
/ 26 января 2019

let curr = arr.shift() удаляет первый элемент из массива и присваивает его curr.

arr.push(...curr.children) добавляет все дочерние элементы в конец массива.

Оба этиОперации изменяют длину массива, и тест 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));
...