ツリー内のノードを再帰的にカウントしない。

Question

最近、インタビューで、このノードクラスを与えられたツリー内のすべてのノードを数えるように求められました。私はインタビューの中で、脳のおならを持っていたものの

class Node 
{ 
    public List<Node> Children; 
} 

iは再帰的にそれをしない数分で今朝これを書きました。

int CountNodes(Node node, int count) 
{ 
    count++; 

    if(node.Children == null) 
     return count; 

    foreach(Node n in node.Children) 
    { 
     count = CountNodes(n, count); 
    } 

    return count; 
} 

しかし、会話中に私たちは再帰的アプローチで問題を議論しました。 1つはスタックオーバーフローです。

これを解決するには、非再帰的な方法は何でしょうか。私はそれに苦しんでいるようだ。

Answer 1

すべてのルートノードを含むList<Node> nodesから始めることができます。この方法は、ノードが存在しなくなるまでループだろう「現在」レベルに残され、各繰り返しで、そのレベルの子供たちと一緒にnodesリストを置き換える：

List<Node> nodes = GetRootNodes(); 
int total = 0; 
while (nodes.Count > 0) 
{ 
    total += nodes.Count; 
    List<Node> children = new List<Node>(); 
    foreach (Node node in nodes) 
    { 
     children.AddRange(node.Children); 
    } 

    nodes = children; 
} 

Answer 2

Breadth-first search

int CountNodes(Node node) 
{ 
    int count = 0; 
    List<Node> nodesToSearch = new List<Node>(); 
    nodesToSearch.Add(node); 

    while(nodesToSearch.Count > 0){ 
     count += nodesToSearch.Count; 

     List<Node> newNodes = new List<Node>(); 
     foreach(Node nodeToSearch in nodesToSearch){ 
      if(nodeToSearch.Children != null) 
       newNodes.AddRange(nodeToSearch.Children); 
     } 
     nodesToSearch = newNodes; 
    } 

    return count; 
}