查找非二叉树深度

Question

我能找到非二叉树深度吗？每个节点可以有多个子节点。我们不知道最大节点数是多少。

public class Node
{
    private List<Node> nodes;
    private string nodeName;

    public Node(string nodeName)
    {
        nodes = new List<Node>();
        this.nodeName = nodeName;
    }

    public List<Node> Nodes
    {
        get { return this.nodes; }
        set { this.nodes = value; }
    }

    protected string NodeName
    {
        get { return this.nodeName; }
    }
}

Answer 1

您可以执行以下操作来计算最大深度（包括根节点）：

public static int Depth(Node root, int depth)
{
    int result = depth + 1;

    foreach (var node in root.Nodes)
        result = Math.Max(result, Depth(node, depth + 1));

    return result;
}

您可以将其称为传入 0 作为初始深度：

int depth = Depth(root, 0);

如果您只想计算所有节点而不是深度：

public static int CountExcludingRoot(Node root)
{
    return root.Nodes.Sum(node => 1 + CountExcludingRoot(node));
}

（这不包括根节点，因此您需要将返回的值加一以获得包括根在内的所有节点的总和）。