c# - 递归树搜索返回错误的结果

Question

我有this implementation树递归函数。它获取从 A 到 D 的所有可能路径。

递归函数是:

private static List<Path> GetPath(int depth, Path path)
{
    if (depth == nodes.Length) 
    {
        return new List<Path> { path };
    }
    else 
    {
        var result = new List<Path>();
        foreach(var link in nodes[depth].Links)
        {
            Node node = new Node { Name = nodes[depth].Name, Links = new[] { link } };
            path.Add(node);

            result.AddRange(
                GetPath(
                    depth+1, path));
        }

        return result;
    }
}

预期的结果应该是:

A1-B2->C3->D4
A1-B5->C3->D4

但是，返回的路径是相同的，它们包括所有可能的节点两次。

函数有什么问题？

Answer 1

foreach(var link in nodes[depth].Links)
{
    Node node = new Node { Name = nodes[depth].Name, Links = new[] { link } };
    path.Add(node);

您可能打算在追加下一个节点之前为您在此处找到的每个节点创建一个新路径(这是 path 的副本)。