如何从给定的父子列表创建树,但不能在其父节点之前创建子节点?

2020-02-22 algorithm tree depth-first-search breadth-first-search

列表包含父级和子级。根节点的父节点为-1。我必须从这里创建一棵树,但是在其父节点之前不能创建任何子节点。

亲子清单

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

Answers

以下算法将起作用:

  1. 初始化从IntegerList/Array[Integer]Map 。在这里, key代表ParentList/Array[Integer]代表Childrens
  2. 遍历有问题的parent child list 。对于每个条目,填充在步骤1中创建的Map 。 即对于问题中提到的示例, Map将如下所示: -1 -> [1] 1 -> [2, 3] 2 -> [4, 5] 3 -> [6, 7] -1 -> [1] 1 -> [2, 3] 2 -> [4, 5] 3 -> [6, 7] -1 -> [1] 1 -> [2, 3] 2 -> [4, 5] 3 -> [6, 7] -1 -> [1] 1 -> [2, 3] 2 -> [4, 5] 3 -> [6, 7]
  3. 一旦你有了Map编制,排序Map的钥匙。
  4. 对于Map每个Key, ValueMap创建节点,然后为其子级创建节点。请遵循此以获取剩余的Key, Value对。

这样可以确保ParentChild之前总是有准备。

Related