algorithm - 如何从给定的父子列表创建树，但子节点不能在其父节点之前创建？

Question

一个列表包含父母和孩子。这里根节点的父节点是-1。我必须从这里创建一棵树，但任何子节点都不能在它成为父节点之前创建。

父子列表

3 7
3 6 
2 5
-1 1
2 4
1 2
1 3

标签： algorithmtreedepth-first-searchbreadth-first-search

Answer 1

以下算法将起作用：

1. 初始化一个Map从Integer到List/Array[Integer]。在这里，key代表Parent和List/Array[Integer]代表Childrens。
2. 迭代parent child list问题中提到的。对于每个条目，填充Map在步骤 1 中创建的。即对于问题中提到的示例，Map将如下所示： -1 -> [1] 1 -> [2, 3] 2 -> [4, 5] 3 -> [6, 7]
3. 准备Map好后，按键排序Map。
4. 对于每个Key, Valuein Map，为父节点创建节点，然后为它的子节点创建节点。遵循此对剩余的Key, Value配对。

这将确保Parent始终做好之前的准备Child。