如何用while/for/foreach循环替代递归遍历Node树并扁平化节点列表？

当然可以使用循环实现节点树的扁平化，避免递归带来的调用栈内存占用问题。常见的迭代方式有**深度优先遍历（使用栈）和广度优先遍历（使用队列）**两种，以下是具体实现：

深度优先遍历（模拟递归的遍历顺序） #

这种方式的遍历顺序和递归的前序遍历一致，代码如下：

using System.Collections.Generic;

public static List<Node> FlattenNodeTreeDepthFirst(Node root)
{
    var flattenedList = new List<Node>();
    if (root == null)
        return flattenedList;

    var nodeStack = new Stack<Node>();
    nodeStack.Push(root);

    while (nodeStack.Count > 0)
    {
        var currentNode = nodeStack.Pop();
        flattenedList.Add(currentNode);

        // 反向推入子节点，保证弹出时的顺序和递归遍历一致
        if (currentNode.HasChildren && currentNode.Children != null)
        {
            for (int i = currentNode.Children.Count - 1; i >= 0; i--)
            {
                nodeStack.Push(currentNode.Children[i]);
            }
        }
    }

    return flattenedList;
}

代码说明： #

• 使用Stack存储待访问的节点，初始时推入根节点
• 每次从栈顶取出节点，加入结果列表
• 反向遍历子节点并推入栈，确保弹出时的顺序和递归前序遍历相同
• 先判断HasChildren和Children是否为空，避免空引用异常

广度优先遍历（按层级顺序遍历） #

如果需要按节点的层级顺序（根节点→第一层子节点→第二层子节点…）扁平化，可使用队列实现：

using System.Collections.Generic;

public static List<Node> FlattenNodeTreeBreadthFirst(Node root)
{
    var flattenedList = new List<Node>();
    if (root == null)
        return flattenedList;

    var nodeQueue = new Queue<Node>();
    nodeQueue.Enqueue(root);

    while (nodeQueue.Count > 0)
    {
        var currentNode = nodeQueue.Dequeue();
        flattenedList.Add(currentNode);

        if (currentNode.HasChildren && currentNode.Children != null)
        {
            foreach (var child in currentNode.Children)
            {
                nodeQueue.Enqueue(child);
            }
        }
    }

    return flattenedList;
}

代码说明： #

• 使用Queue存储待访问的节点，初始时入队根节点
• 每次从队首取出节点，加入结果列表
• 按顺序将子节点入队，保证层级遍历的顺序
• 同样做了空值判断，避免异常

这两种迭代方式都不会产生递归调用栈的内存开销，仅需维护栈/队列和结果列表的内存，适用于大型节点树的扁平化处理。

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