不使用递归处理嵌套项目列表

Question

我有一个名为Item的类，如下所示:

public class Item
{
   public string Name { get; set; }
   public int Value { get; set; }
   public List<Item> SubItems { get; set; }
}

项可以嵌套超过n个级别，这意味着任何项都可以包含一个项目列表，其中每个项目都包含一个项目列表...

我想编写一个接受item实例作为参数并返回所有嵌套项的value总和的方法。

我的当前递归方法如下所示：

public int GetSumOfValue(Item item)
{
   int sum = item.Value;
   if (item.SubItems == null)
   {
      return sum;
   }

   foreach (var subItem in item.SubItems)
   {
      sum += GetSumOfValue(subItem);
   }
   return sum;
}

虽然这样做可以运行，但据我所知，使用循环的迭代方法在大多数情况下会更快。

（请注意，出于简洁起见，我对该方法进行了抽象和缩短。这不是生产代码。）

由于有嵌套类，我很难想出如何将我的递归方法转换为迭代方法。

如果您有任何提示，感激不尽。谢谢。

- axel g

---

理论计算机科学的一个基本概念是，任何递归算法都可以用迭代形式来写。然而，如上所述，在最坏情况下，这意味着需要创建一个替换系统堆栈的数据结构——这在内存或性能方面并没有太大收益。你估计你的树的最大深度是多少？ - PMF

我删除了我的评论，因为它说“我不明白你怎么能使这个非递归”，这让我看起来很蠢。无论如何，正如我所说：（递归）方法调用可能会以堆栈帧的形式添加一些开销，但这真的会对你的性能造成可衡量的损害吗？或者你是过早优化，还是这只是一个学术问题？ - CodeCaster

@CodeCaster 没关系。那是我从那些课程中唯一记得的几件事之一。 - PMF

Answer 1

您可以使用一个Queue<Item>来收集所有项目：

public static int GetSumOfValue(Item item)
{
    if(item == null) 
    {
        throw new ArgumentNullException(nameof(item), "item must not be null");
    }

    int totalSum = 0;
    Queue<Item> queue = new Queue<Item>();
    queue.Enqueue(item);

    while (queue.Count > 0)
    {
        Item current = queue.Dequeue();
        totalSum += current.Value;
        foreach (Item subItem in current?.SubItems ?? Enumerable.Empty<Item>())
        {
            queue.Enqueue(subItem);
        }
    }

    return totalSum;
}

- Tim Schmelter

---

你是第一个实现BFS（广度优先搜索）的人。 - Dmitry Bychenko

totalSum += current.Value 可能会导致 null 引用错误吗？ - Thomas Ayoub

只有在一开始将 null 添加到队列中，才能使用 @Thomas。 - CodeCaster

@ThomasAyoub：添加了样板代码以检查无效参数。 - Tim Schmelter

就这个特定情况而言，我同意。但在一般情况下，由于访问顺序可能会有所不同。我提到了这一点，以防有人想要在没有递归的情况下实现精确的行为（对于顺序很重要的情况）。 - wohlstad

Answer 2

这是一个使用 Linq 的可能解决方案：

//test case 1
List<Item> items = new List<Item> 
{ 
    new Item { Name = "a", Value = 1, SubItems = new List<Item> { new Item { Name = "b", Value = 2, SubItems = new List<Item> { new Item { Name = "c", Value = 3, SubItems = null } } } } } 
};

//test case 2
List<Item> items2 = new List<Item> 
{ 
    new Item { Name = "a", Value = 1, SubItems = new List<Item> { new Item { Name = "b", Value = 2, SubItems = new List<Item> { new Item { Name = "c", Value = 3, SubItems = null } } } } },
    new Item { Name = "a", Value = 0, SubItems = new List<Item> { new Item { Name = "b", Value = 0, SubItems = new List<Item> { new Item { Name = "c", Value = 1, SubItems = null } } } } },
    new Item { Name = "a", Value = 0, SubItems = new List<Item> { new Item { Name = "b", Value = 0, SubItems = new List<Item> { new Item { Name = "c", Value = 1, SubItems = new List<Item> { new Item { Name = "c", Value = 1, SubItems = null } } } } } } } 
};

//test case 3
Item item = new Item { Name = "a", Value = 1, SubItems = new List<Item> { new Item { Name = "b", Value = 2, SubItems = new List<Item> { new Item { Name = "c", Value = 3, SubItems = null } } } } };
        
Console.WriteLine(SumItems(items)); //prints 6
Console.WriteLine(SumItems(items2)); //prints 9
Console.WriteLine(SumItem(item)); //prints 6

public class Item
{
   public string Name { get; set; }
   public int Value { get; set; }
   public List<Item> SubItems { get; set; }
}

//Just pass your singular item as a list with your top level item
//or I provided another implementation below that takes a single Item
public int SumItems(List<Item> items)
{
    int total = 0;
    while(true)
    {
        if(items == null || items.Count < 1)
            break;
        //sum the current level
        total += items.Sum(b => b.Value);
        //get a flat list of siblings
        items = items.SelectMany(a => a.SubItems ?? new List<Item>()).ToList() ?? new List<Item>();         
    }
    return total;
}

//singular method
public int SumItem(Item item)
{
    int total = 0;
    if(item == null)
       return total;

    if(item.SubItems == null || item.SubItems.Count < 1)
       return item.Value;
    
    total += item.Value;
    total += SumItems(item.SubItems);

    return total;
}

- Ryan Wilson