python - 给定根构造树

Question

例如。 [13,11], [13,8], [6, 8], [3, 6]其中根为 1

寻找一种 Pythonic 方式将树构造成字典，这样我们就有 {13: [11, 8], 11: [], 3: [], 6: [3], 8: [6]}

因为我知道根，所以我的方法是用 13 遍历条目，连接它们，然后将这些条目视为根，依此类推。

注意没有顺序。为了区分，我知道根(某个数字)并且可以从那里确定。

有没有更好的办法？

Answer 1

通过使用 set 来跟踪哪些元素已添加到字典中，我们可以在 O(n) 时间内解决此问题。总体思路是遍历节点，检查节点当前是否在图中，如果是，我们在添加到字典时知道它是父节点。

from collections import defaultdict

class MyTree:
    def __init__(self, data):
        self.data = defaultdict(list)
        self.seen = set()

        for node in data:
            self.add_node(node)

        for el in self.seen:
            if el not in self.data:
                self.data[el] = []

    def add_node(self, el):
        x, y = el

        if y in self.seen:
            self.data[y].append(x)
        else:
            self.data[x].append(y)

        self.seen.update(el)

在行动中:

arr = [[1,2], [1,8], [5, 8], [3, 5]]

x = MyTree(arr)
print(x.data)

defaultdict(<class 'list'>, {1: [2, 8], 8: [5], 5: [3], 2: [], 3: []})