def paths(tree):
#Helper function
#receives a tree and
#returns all paths that have this node as root and all other paths
if tree is the empty tree:
return ([], [])
else: #tree is a node
root = tree.value
rooted_paths = [[root]]
unrooted_paths = []
for subtree in tree.children:
(useable, unueseable) = paths(subtree)
for path in useable:
unrooted_paths.append(path)
rooted_paths.append([root]+path)
for path in unuseable:
unrooted_paths.append(path)
return (rooted_paths, unrooted_paths)
def the_function_you_use_in_the_end(tree):
a,b = paths(tree)
return a+b
使用深度优先搜索查找树中每个节点的路径,然后调用
enumerate-paths(Path p)
,其中p
是从根到节点的路径。假设路径p
是节点数组,其中p[0]
是根,而p[n]
是当前节点。这些路径中的每个都是不同的,并且每个路径都不同于从树的任何其他节点返回的结果,因为没有其他路径以
p[n]
结尾。显然它是完整的,因为任何路径都是从一个节点到它和根之间的某个节点的。它也是最优的,因为它能准确地找到并输出每条路径一次。顺序与您的稍有不同,但您始终可以创建路径列表,其中
A[x]
是长度为x
的路径列表。然后可以按路径的长度顺序输出路径,尽管这需要O(n)存储空间。还有一个办法:
树中没有重复的每一条路径都由它的开始和结束来唯一地描述。
所以枚举路径的方法之一就是枚举每一对可能的顶点。对于每一对,找到路径相对容易(找到共同的祖先并通过它)。
每当在树上发现问题时,只要使用递归:D
相关问题 更多 >
编程相关推荐