与えられたレベルの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（）は、配列要素ごとに1回コールバック関数を実行します。 map（）やreduce（）と異なり、常に未定義の値を返し、連鎖はできません。典型的な使用例は、チェーンの終わりに副作用を実行することです。 - 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

あなたは近かったです。あなたはちょうど子供の長さをどこかに保管しなければなりませんでした。

目的のレベルより1レベル低い値に達すると、関数は子の長さを返します。

ツリーの上位にあるすべてのノードは、子ノードから収集された値をゼロに加算し、ルートノードに達するまでそれを戻します。

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

このアプローチの問題点は、所望のレベルは、ツリーの深さよりも大きいか、またはそれがゼロである場合（ルートレベル、1を返すべき）場合0が返されることです。

これを解決するには、クロージャを行い、問題のある値をチェックすることができます。

また、毎回手動で開始レベルを送信する必要はありません。

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