如何递归实现多层级节点列表的前序二叉树格式排序？

核心思路 #

• 先构建父节点到子节点的映射字典，方便快速查找任意节点的子节点，避免重复遍历原列表
• 递归遍历逻辑：先将当前节点加入结果列表，再依次递归处理该节点的所有子节点，完全匹配前序遍历的逻辑
• 多根节点场景：直接遍历所有Level 1节点，逐个启动递归流程

C# 代码实现 #

using System.Collections.Generic;
using System.Linq;

public class Test
{
    public int Id;
    public int Level;
    public int? ParentId; // 建议改为可空类型，适配Level 1节点无父ID的场景
}

public static class NodeProcessor
{
    public static List<Test> ConvertToPreOrder(List<Test> originalNodes)
    {
        // 构建父ID到子节点列表的映射
        var childNodeMap = originalNodes
            .Where(node => node.ParentId.HasValue)
            .GroupBy(node => node.ParentId.Value)
            .ToDictionary(group => group.Key, group => group.ToList());

        var preOrderResult = new List<Test>();

        // 遍历所有Level 1节点，启动递归
        foreach (var rootNode in originalNodes.Where(node => node.Level == 1))
        {
            TraversePreOrder(rootNode, childNodeMap, preOrderResult);
        }

        return preOrderResult;
    }

    private static void TraversePreOrder(Test currentNode, Dictionary<int, List<Test>> childNodeMap, List<Test> result)
    {
        // 前序遍历：先加入当前节点
        result.Add(currentNode);

        // 若当前节点有子节点，递归遍历每个子节点
        if (childNodeMap.TryGetValue(currentNode.Id, out var childNodes))
        {
            foreach (var child in childNodes)
            {
                TraversePreOrder(child, childNodeMap, result);
            }
        }
    }
}

代码说明 #

• 映射字典childNodeMap通过Linq分组构建，时间复杂度O(n)，后续查找子节点为O(1)，整体效率远高于嵌套循环
• 递归方法TraversePreOrder逻辑简洁，完全贴合前序遍历的定义，最多5层的限制不影响递归，递归会自动终止于无子节点的节点
• 将ParentId改为可空类型int?是更严谨的写法，符合"Level 1节点无父ID"的业务场景

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