在最近的一次採訪中,我被要求在給定這個節點類的樹中統計所有節點。非遞歸地計算樹中的節點。
class Node
{
public List<Node> Children;
}
雖然我在面試過程中有腦屁我在做它遞歸幾分鐘今天早上寫了這一點。
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;
}
但是在會話期間,我們討論了遞歸方法的問題。一個是堆棧溢出。
什麼是非遞歸方法來解決這個問題。我似乎正在努力。
所以,你實現[深度優先搜索](https://en.wikipedia.org/wiki/Depth-first_search) - 另一種選擇是[廣度優先搜索](https://en.wikipedia.org/wiki/Breadth-first_search ),這基本上是[尾遞歸](https://en.wikipedia.org/wiki/Tail_call)。最後,如果你控制Node的實現,當子節點被添加時(根節點),你也可以在Node節點上增加一個子節點。 –
通常的方法是使用隊列。該算法非常簡單:首先添加根節點。然後,當隊列不爲空時:出列隊列,對其執行任何操作,然後將其所有子隊列添加到隊列中,重複。 –