Как создать дерево из заданного родительского дочернего списка, но дочерний узел не может быть создан до его родительского узла?

Question

Список содержит родителей и детей. Здесь родительский узел root равен -1. Я должен создать дерево отсюда, но ни один дочерний узел не может быть создан до того, как он станет родительским.

Список родительских дочерних элементов

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

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, выполните сортировку * 1020. * по ключам.
4. Для каждого Key, Value в Map создайте узел для родительского элемента, а затем для его дочернего элемента. Следуйте этому для оставшихся Key, Value Pair.

Это гарантирует, что Parent всегда будет подготовлен до Child.