在 C# 中保持对嵌套列表 <T> 的引用

Question

我的任务是在一棵树中找到路径，其中节点的总和为开头给出的特定总和。

示例：

在我的实现中，我将结果保存在嵌套列表中，如下所示：

private void DfsPathGivenSum(Tree<T> node, List<T> list, int sum, List<List<T>> results)
{
    list.Add(node.Key);

    foreach (var child in node.children)
    {
        this.DfsPathGivenSum(child, list, sum, results);
    }

    var currentPathSum = list.Sum(x => int.Parse(x.ToString()));
    if (currentPathSum == sum)
    {
        results.Add(list);
    }

    list.RemoveAt(list.Count - 1);
}

当我从另一个方法调用这个方法时：

public List<List<T>> PathsWithGivenSum(int sum)
{
    var list = new List<T>();
    var results = new List<List<T>>();
    this.DfsPathGivenSum(this, list, sum, results);

    return results;
}

对内部 List 的引用似乎丢失了。我该如何处理这个问题？

Answer 1

改变

results.Add(list);

至

results.Add(list.ToList());

即你想在将当前列表添加到结果时创建一个副本，否则你将只有一堆对同一个列表的引用，最后将是空的。

我还建议一些比 ToString 和 int.Parse 更好的方法将节点转换为数字。例如，通过采用可以提供给 .sum 方法的 Func<T, int> 参数。

您还可以通过保持运行总和来稍微改进算法，以避免需要为每个访问的节点遍历所有先前的节点。

Answer 2

正如@JonasH 所说，您肯定需要从复制的节点集合开始工作。

// Pseduocode:
// For each node
//   Find Path and Sum
//   If Sum correct
//     Add Path to Result


private class Node
{
    public Node Parent;
    public int score;
}

private void DfsPathGivenSum(List<Node> allNodes, int targetSum, List<List<Node>> results) {

    results.Clear();

    // Copy list of Nodes into Queue
    var pending = new Queue<Node>(allNodes); 

    // For each node in queue
    while (pending.Count > 0) {
        var currentNode = pending.Dequeue();

        // Create 'new' Path trace starting at currentNode
        var path = new List<Node> { currentNode };
        var sum = currentNode.score;

        // Iterate until at root node
        while (currentNode.Parent != null) { 
            currentNode = currentNode.Parent; // step to parent node
            path.Add(currentNode); // add to trace
            sum += currentNode.score; // add to sum
        }

        if (sum == targetSum)
            results.Add(path);
    }
}

在 C# 中保持对嵌套列表 <T> 的引用

Keeping reference to a nested List<T> in C#

c#

tree

reference

data-structures