Получить количество узлов на заданном уровне дерева JSON

Question

У меня есть древовидная структура JSON с узлами, у которых есть дочерние элементы, и я хотел бы знать, сколько узлов существует на заданном уровне структуры. В настоящее время у меня есть эта рекурсивная структура:

var getNumNodesAtLevel = function (node, curr, desired) { 
     if (curr === (desired - 1)) { 
      return node.children.length; 
     } else { 
      var children = node.children; 
      children.forEach(function (child) { 
       return getNumNodesAtLevel(child, curr + 1, desired); 
      }); 
     } 
    }; 

Это не сработает - любая помощь будет оценена!

Answer 1

Существует несколько недостатков с подходом, который вы здесь видите.

Остановка в первый раз, при котором обнаруживается глубина глубины цели, будет подсчитываться только первый набор детей, который будет только подмножеством.

Использование функции итерации, такой как forEach, вызовет вызовы в своих итерациях, но не вернет само значение, а также показанный подход использования возврата внутри обратного вызова не влияет.

forEach() выполняет функцию обратного вызова один раз для каждого элемента массива; в отличие от map() или reduce() он всегда возвращает значение undefined и не связывается с цепочкой. Типичным примером использования является выполнение побочных эффектов в конце цепи. - MDN: Array.prototype.forEach()

Лучшим подходом было бы проанализировать всю структуру дерева для ширины по глубинам и после завершения вернуть индексированное значение. Это можно коротко закоротить, не рекурсивного после заданной глубины, но я оставил в полном анализе в объекте depths для полного примера.

Как показано ниже, это использует IIFE для рекурсии дерева, для создания объекта, чей ключ является глубиной и значением которого является ширина, а затем возвращает связанную ширину на основе глубины ввода от исходного вызова функции.

var testObj = { 
 
children : [ 
 
    { children : [ { children : [ ] } ] }, 
 
    { children : [ ] }, 
 
    { children : [ { children : [ ] } ] } 
 
] 
 
}; 
 

 
var getNumNodesAtLevel = 
 
    function (root, depth) { 
 
     var depths = {0:1}; 
 

 
     (function recurTree(node,level){ 
 
     level++; 
 
     
 
     if(depths[level] == void 0){ 
 
      depths[level] = node.children.length; 
 
     }else{ 
 
      depths[level] += node.children.length; 
 
     } 
 

 
     //optionally short circuit to avoid excessive recursion 
 
     //if(level+1 > depth) return; 
 
     for(var i = 0; i < node.children.length; i++){ 
 
      recurTree(node.children[i],level); 
 
     } 
 
     })(root,0) 
 
     
 
     return depths[depth]; 
 
    }; 
 

 
console.log(getNumNodesAtLevel(testObj,1)); 
 
console.log(getNumNodesAtLevel(testObj,2));

Answer 2

Вы были близки. Вы просто должны были где-то хранить детскую длину.

Как только один уровень меньше желаемого, функция возвращает длину детей.

Все узлы, расположенные выше в дереве, просто добавят значения, полученные от детей, в ноль и передают их до тех пор, пока не будет достигнут корневой узел.

var getNumNodesAtLevel = function(node, curr, desired) { 
    if (curr === (desired - 1)) 
    return node.children.length; 

    var count = 0; 
    node.children.forEach(function(child) { 
    count += getNumNodesAtLevel(child, curr + 1, desired); 
    }); 
    return count; 
}; 

Проблема с этим подходом является то, что 0 будет возвращено, когда желаемый уровень больше, чем глубина дерева или когда оно равно нулю (корневой уровень, должен возвращать 1).

Чтобы исправить это, вы можете сделать закрытие и проверить наличие проблемных значений.

Также не обязательно посылать начальный уровень вручную каждый раз.

var test = { 
 
children : [ 
 
    { children : [ { children : [ ] } ] }, 
 
    { children : [ ] }, 
 
    { children : [ { children : [ ] } ] } 
 
] 
 
}; 
 

 
var getNumNodesAtLevel = (function() { 
 

 
    var getNumNodesAtLevel = function(node, curr, desired) { 
 
    if (curr === (desired - 1)) 
 
     return node.children.length; 
 

 
    var count = 0; 
 
    node.children.forEach(function(child) { 
 
     count += getNumNodesAtLevel(child, curr + 1, desired); 
 
    }); 
 
    return count; 
 
    }; 
 

 
    return function(root, desired) { 
 

 
    if (desired === 0) 
 
     return 1; 
 

 
    var count = getNumNodesAtLevel(root, 0, desired); 
 
    if (count === 0) 
 
     return null; // you could throw an error here 
 

 
    return count; 
 

 
    }; 
 

 
}()); 
 

 
console.log(getNumNodesAtLevel(test, 0)); // 1 
 
console.log(getNumNodesAtLevel(test, 1)); // 3 
 
console.log(getNumNodesAtLevel(test, 2)); // 2 
 
console.log(getNumNodesAtLevel(test, 3)); // null 
 
console.log(getNumNodesAtLevel(test, 4)); // null