javascript - 获取 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)将在迭代中进行调用，但它本身不会返回值，并且在回调内部使用 return 的方法也没有效果。

forEach() executes the callback function once for each array element; unlike map() or reduce() it always returns the value undefined and is not chainable. The typical use case is to execute side effects at the end of a chain. -MDN: Array.prototype.forEach()

更好的方法是按深度分析整个树结构的宽度，完成后返回索引值。可以通过在给定深度之后不递归来短路此问题，但我将完整的分析留在了对象 深度 中以获取完整的示例。

如下所示，它使用 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));