如何通过“冒泡”每个子树的值来展平树？

Question

我有以下树数据结构：

class TreeNode:

    def __init__(self, path, value=None):

        self.path = path

        self.value = value

        self.children = []

path目录或文件名在哪里。如果 的值为path文件（树中的叶子），则值为整数，否则为None. 这是此树结构的示例：

└── root (None)

    ├── dir0 (None)

    |   ├── dir00 (None)

    |   |   └── file000.txt (10)

    |   └── file00.txt (10)

    ├── dir1 (None)

    |   └── file10.txt (5)

    ├── dir2 (None)

    |   ├── file20.txt (10)

    |   └── file21.txt (15)

    └── dir3 (None)

        ├── dir30 (None)

        |   └── file300.txt (15)

        └── file30.txt (10)

我正在尝试返回已解决路径及其关联的最小可能展平列表value。如果子树中的所有节点都具有相同的value，那么我们说这样的子树与value它的节点相同。本质上，value如果父节点的所有子节点都具有相同的value.

例如，上面的树应该返回的是：

/root/dir0: 10

/root/dir1: 5

/root/dir2/file20.txt: 10

/root/dir2/file21.txt: 15

/root/dir3/dir30: 15

/root/dir3/file30.txt: 10

我尝试了几种不同的方法来实现这一点：用堆栈遍历树，用递归遍历树，以及使用集合；一切都失败了。我最近尝试的伪代码如下所示：

def build_list(self, treenode):

    if treenode.value:

        return [(treenode.path, treenode.value)]

    if treenode.value == None:

        s = set()

        for child in treenode.children:

            potential_values = self.build_list(child)

            for val in potential_values:

                s |= {val[1]}

        if len(s) == 1:

            return [(treenode.path, treenode.value)]

        else:

            return [(child.path, child.value) for child in treenode.children]

我将如何做到这一点？伪代码完全没问题，我正在寻找一种方法，不一定是完整的实现。

Answer 1

方法一递归应该起作用：def recurse_update_value(treenode):    if not treenode.children:        return    for child in treenode.children:        recurse_update_value(child)    if all(x.value==treenode.children[0].value for x in treenode.children):        treenode.value = treenode.children[0].value        treenode.children = []方法二此外，如果您可以编辑 TreeNode 类，则可以将 getter 方法设置为自动更新子类。class TreeNode:    def __init__(self, path, value=None):        self.path = path        self._value = value        self.children = []    @property    def value(self)        if not self.children:            return self._value        first_child_value = self.children[0].value        if all(x.value==first_child_value for x in self.children)            self._value = first_child_value            self.children = []        return self._value然后，您只需调用topnode.value即可更新树。

Answer 2

这是一种方法。我正在使用不同的节点类来使设置更容易一些：class TreeNode:&nbsp; &nbsp; def __init__(self, node_id, value=None):&nbsp; &nbsp; &nbsp; &nbsp; self.node_id = node_id&nbsp; &nbsp; &nbsp; &nbsp; self.value = value&nbsp; &nbsp; &nbsp; &nbsp; self.children = []&nbsp; &nbsp; def addChildren(self, *node_list):&nbsp; &nbsp; &nbsp; &nbsp; self.children += node_list&nbsp; &nbsp; def __repr__(self):&nbsp; &nbsp; &nbsp; &nbsp; return f'<TreeNode(node_id={self.node_id}, value={self.value})'__repr__()只是为了在打印时获得人类可读的实例表示。我试图设置树来反映您的示例，但如果它不完全正确，请随时告诉我。（它可以做得更简洁，但为了清楚起见，我已经为每个对象写了一行。）root = TreeNode('root')dir0 = TreeNode('dir0')dir00 = TreeNode('dir00')file00 = TreeNode('file00', 10)file000 = TreeNode('file000', 10)dir1 = TreeNode('dir1')file10 = TreeNode('file10', 5)dir2 = TreeNode('dir2')file20 = TreeNode('file20', 10)file21 = TreeNode('file21', 15)dir3 = TreeNode('dir3')dir30 = TreeNode('dir30')file30 = TreeNode('file30', 10)file300 = TreeNode('file300', 15)root.addChildren(dir0, dir1, dir2, dir3)dir0.addChildren(dir00, file00)dir00.addChildren(file000)dir1.addChildren(file10)dir2.addChildren(file20, file21)dir3.addChildren(dir30, file30)dir30.addChildren(file300)现在对于递归函数：def buildList(node):&nbsp; &nbsp; # Return node id and value if no children&nbsp; &nbsp; if not node.children:&nbsp; &nbsp; &nbsp; &nbsp; return [(node.node_id, node.value)]&nbsp; &nbsp; # Call buildList on each child and get distinct values&nbsp; &nbsp; childitems = [item for child in node.children for item in buildList(child)]&nbsp; &nbsp; childvalues = set(childitem[1] for childitem in childitems)&nbsp; &nbsp; # If value is unique, return this node as if it has the unique value&nbsp; &nbsp; if len(childvalues) == 1:&nbsp; &nbsp; &nbsp; &nbsp; return [(node.node_id, childvalues.pop())]&nbsp; &nbsp; # Otherwise, return all results&nbsp; &nbsp; return childitems这会产生以下输出：>>> buildList(root)[('dir0', 10),&nbsp;('dir1', 5),&nbsp;('file20', 10),&nbsp;('file21', 15),&nbsp;('dir30', 15),&nbsp;('file30', 10)][编辑] 请注意，这将返回一个列表并且不会改变节点。关于您的特定实现，您可能想考虑如果有一个空目录会发生什么。这是允许的吗？如果是这样，它是一片叶子，而不是一个文件。在这种情况下它会有价值吗？