非递归实现嵌套Item类的Value总和计算方法问询

要把递归逻辑转成迭代，核心是手动用栈或队列模拟递归的调用栈过程，把所有待处理的Item都放进容器里，逐个取出累加Value，再把它的子项加入容器继续处理。下面给两种常用实现：

深度优先迭代（和递归遍历顺序一致） #

用栈来实现，和递归的处理顺序完全相同，先处理父节点，再深度遍历子节点：

public int GetSumOfValueIterative(Item item)
{
    if (item == null)
        return 0;
        
    int sum = 0;
    Stack<Item> stack = new Stack<Item>();
    stack.Push(item);
    
    while (stack.Count > 0)
    {
        var currentItem = stack.Pop();
        sum += currentItem.Value;
        
        // 栈是后进先出，倒序加入子项可以保证和递归的遍历顺序一致（不影响总和，可选）
        if (currentItem.SubItems != null)
        {
            for (int i = currentItem.SubItems.Count - 1; i >= 0; i--)
            {
                stack.Push(currentItem.SubItems[i]);
            }
        }
    }
    
    return sum;
}

广度优先迭代 #

用队列实现，先处理同一层级的所有节点，再处理下一层级，最终总和和深度优先完全一致：

public int GetSumOfValueBFS(Item item)
{
    if (item == null)
        return 0;
        
    int sum = 0;
    Queue<Item> queue = new Queue<Item>();
    queue.Enqueue(item);
    
    while (queue.Count > 0)
    {
        var currentItem = queue.Dequeue();
        sum += currentItem.Value;
        
        if (currentItem.SubItems != null)
        {
            foreach (var subItem in currentItem.SubItems)
            {
                queue.Enqueue(subItem);
            }
        }
    }
    
    return sum;
}

关键逻辑说明 #

• 递归是靠程序的调用栈自动保存待处理节点，迭代就是自己用容器来存这些节点
• 两种实现的核心步骤都是：
  1. 把根节点放进初始化好的容器
  2. 循环取出节点，累加Value
  3. 若节点有子Item，全部加入容器
  4. 容器为空时返回总和
• 两种方式性能差异可以忽略，选哪种看你是否需要和递归保持一样的遍历顺序（深度优先）

内容的提问来源于stack exchange，提问作者axel g