python - 如何查找从根到节点的路径（python 3.6）

Question

我试图找到从 ROOT 到某个 VALUE 的节点的树的所有路径。

我尝试的第一个解决方案是使用当节点的值 == 值时停止的递归：

def list_paths_to_value(t, value):
    list_ = []

    for b in t.branches:
        list_ += [[t.label] + path for path in list_paths_to_value(b, value)]

    if t.label == value:
        return [[t.label]]
    return list_

one_branch_two_depth = Tree(1, [Tree(2, [Tree(2)])])

list_paths_to_value(one_branch_two_depth, 2)

Output:
[[1,2]]

输出应该是 [[1,2], [1,2,2]] 但我的输出无法返回 [1,2,2] 路径。

我的另一个解决方案是强制递归函数只停在树的叶子上：

def list_paths_to_value(t, value):
    list_ = []

    for b in t.branches:
        list_ += [[t.label] + path for path in list_paths_to_value(b, value)]

    if t.label == value and t.is_leaf():
        return [[t.label]]

    return list_

one_branch_two_depth = Tree(1, [Tree(2, [Tree(2)])])

list_paths_to_value(one_branch_two_depth, 2)

Output:
[[1,2,2]]

另一方面，这并没有返回 [1,2] 值。

非常感谢有关如何返回预期输出的指导。

标签： pythonpython-3.xrecursiontree

Answer 1

还附加树类的代码：

class Tree:
    def __init__(self, label, branches=[]):
        for b in branches:
            assert isinstance(b, Tree)
        self.label = label
        self.branches = list(branches)

    def is_leaf(self):
        return not self.branches