使用对象列表构建树

Question

我有一个具有属性id和parent_id的对象列表.
我想建一棵树来连接那些孩子和父母.
1个父母可能有几个孩子,并且有一个对象将成为所有对象的祖先.

实现它的最快算法是什么？
我使用C#作为编程语言,但其他语言也没问题.

Answer 1

像这样的事情应该可以解决问题：

public List<Node> MakeTreeFromFlatList(IEnumerable<Node> flatList)
{
    var dic = flatList.ToDictionary(n => n.Id, n => n);
    var rootNodes = new List<Node>();
    foreach(var node in flatList)
    {
        if (node.ParentId.HasValue)
        {
            Node parent = dic[node.ParentId.Value];
            node.Parent = parent;
            parent.Children.Add(node);
        }
        else
        {
            rootNodes.Add(node);
        }
    }
    return rootNodes;
}

（假设 ParentId 是 a Nullable<int>，对于根节点为 null）