python - 在Python中递归地使用Parents数组查找路径

Question

所以我有一个任务，即编写一个函数，它接受遍历生成的父数组、起始顶点和结束顶点，并生成从起始顶点到结束顶点的路径。

我已经尝试为此编写代码

def tree_path(parents, start, end):
    if ((start == end) or (end == -1)):
        return [start, end]
    else:
        return tree_path(parents, start, parents[end])

它没有达到我的预期目的。我不太擅长递归。任何帮助将非常感激。谢谢

Answer 1

假设我们想要从 start 到 end 的所有顶点的列表，您可以尝试以下操作:

def tree_path(parents, start, end):
    if (start == end) or (end == -1):
        return [start]
    else:
        return tree_path(parents, start, parents[end]) + [end]

如果start与end重合，那么我们的路径仅包含一个顶点:start。否则，我们找到从 start 到 end 的父级的路径，并向该路径添加 end 节点。