c++ - 如何从节点的父节点列表构建树？

Question

我知道每个节点的父节点。它存储在平面 unordered_map 中。每个节点只是一个数字，其中零表示根。我怎样才能根据这些信息有效地创建树？

struct node {
    int id;
    unordered_set<node> children;
};

可能会出现某些节点根本没有附加到根的情况。那些分离的链可以忽略，不需要成为结果树的一部分。

如果需要，请询问更多信息。

Answer 1

创建一个节点指针数组。

然后遍历映射，将数组中给定索引处的节点添加到其父数组中索引处节点的 children。

然后索引 0 处的节点将成为树的根。