时间戳

首页 > 解决方案 > 在树中查找值的路径

python - 在树中查找值的路径

问题描述

想象一下，你要编写一个函数，它接受一个树和一个值 x 作为参数。该函数必须以列表的形式返回从树根到该值的所有路径。如果有多个路径，则该函数返回列表列表。

这是我到目前为止得到的

def path_finder(t,value):
    paths = []
    if label(t) == value:
       return [label(t)]
    for b in branches(t):
       path = path_finder(b, value)
       if path:
         paths.append([label(t)]+path)
    return paths

但是，给定树 t 和值 x = 5，这是我的输出

t = tree(1, [tree(2, [tree(3), tree(4, [tree(6)]), tree(5)]), tree(5)])

path_finder(t,5)

[[1,[2,5]],[1,5]]

似乎是堆叠问题。

任何帮助调试它？

注意：label(t) --> 根的值

标签： pythonbinary-tree

解决方案

我不知道您是否正在使用标准的树类，所以我做了一个。

class tree():
    def __init__(self, val, sub=[]):
        self.val = val
        self.sub = sub # a list of trees

def label(t):
    return t.val
def branches(t):
    return t.sub

def path_finder(t, value):
    paths = []
    if label(t) == value:
        paths.append([value])
    for b in branches(t):
        paths += [[label(t)] + path for path in path_finder(b, value)]
    return paths

t = tree(1, [tree(2, [tree(3), tree(4, [tree(6)]), tree(5)]), tree(5)])
for x in range(7):
    print(x, path_finder(t, x))

主要修正是在线paths += [[label(t)] + path for path in path_finder(b, value)]。另请注意，当 时label(t) == value，我不会立即返回列表。在那一刻停止代码不会找到所有路径，例如，当节点 5 在另一个节点 5 下时。

输出：

# 0 [] # when path_finder cannot find the value
# 1 [[1]]
# 2 [[1, 2]]
# 3 [[1, 2, 3]]
# 4 [[1, 2, 4]]
# 5 [[1, 2, 5], [1, 5]]
# 6 [[1, 2, 4, 6]]

推荐阅读