У меня есть словарь Python, где мне нужно найти детей узлов, если таковые имеются

Question

У меня есть следующий словарь, представляющий id:parent. {1: 2, 3: 1}.

Мне нужно выполнить цикл и проверить, если id == parent, то это потомок.

Например, здесь: 1=1, поэтому 3 является потомком 1.

Я добавлю его в словарь соответственно.Есть идеи?

 d={1:2, 3:1}
      for node in d:

Answer 1

Решением O(n) будет:

child_parent = {1:2, 3:1, 4:1, 5:2, 1:5, 6:5, 7:2}
parent_children = {}
for child, parent in child_parent.items():
    parent_children.setdefault(parent, []).append(child)

, дающее:

{5: [1, 6], 1: [3, 4], 2: [5, 7]}

---

И, для простоты оценки, данные представляют собой следующее дерево:

  2
 / \
7   5
   / \
  6   1
     / \
    3   4

Answer 2

dict1={1:2,2:3,3:1,4:1,5:2}
result={}
for key in dict1.keys():
    result[key]=[]
    for item in dict1.items():
        if key==item[1]:
            result[key].append(item[0])
print(result)  

output:
   {1: [3, 4], 2: [1, 5], 3: [2], 4: [], 5: []}

Если вы не хотите, чтобы эти идентификаторы были без дочерних, вы можете написать следующим образом.

dict1={1:2,2:3,3:1,4:1,5:2}
result={}
for key in dict1.keys():
    for item in dict1.items():
        if key==item[1]:
            if key not in result:
                result[key]=[]
            result[key].append(item[0])
print(result)
output:
{1: [3, 4], 2: [1, 5], 3: [2]}