我正在尝试解决以下问题:找到树中最重节点的权重,并将该节点表示为列表。这就是我想出的,但我很确定这是一个非常混乱的解决方案。有什么建议可以在给定的课堂框架内更有效地做到这一点吗?
给定类:
class Tree_node():
def __init__(self,key,val):
self.key=key
self.val=val
self.left=None
self.right=None
def __repr__(self):
return "[" + str(self.left) + " " + str(self.key) + " " +
str(self.val) + " " + str(self.right) + "]"
我计算最重路径的重量:
def weight(node):
if node == None:
return 0
if weight(node.left)>weight(node.right):
return node.val+weight(node.left)
else:
return node.val+weight(node.right)
然后我尝试将最重的路径作为列表返回:
def heavy_path(node):
if node==None:
return []
elif node.val+weight(node.left)> node.val+weight(node.right):
return [node.val] + filter_values(path_values(node.left))
else:return [node.val] + filter_values(path_values(node.right))
def path_values(node):
if node == None:
return 0
return [node.val,path_values(node.left),path_values(node.right)]
def filter_values (node):
values = []
sub_lists = []
if node != 0:
for value in node:
if isinstance(value, list):
sub_lists = filter_values(value)
else:
if value != 0:
values.append(value)
return values+sub_lists
因此,给定像 [[None a 7 None] b 5 [[None c 8 None] d 3 None]] 这样的树:
>>> weight(t)
16
>>> heavy_path(t)
[5, 3, 8]
有什么更好的方法呢?
假设您将最重的路径解释为始终从树根开始并下降到一片叶子的路径。您可以尝试合并权重查找和路径构建操作:
def heavy_path(node):
if not node
return (0,[])
[lweight,llist] = heavy_path(node.left)
[rweight,rlist] = heavy_path(node.right)
if lweight>rweight:
return (node.val+lweight,[node.val]+llist)
else:
return (node.val+rweight,[node.val]+rlist)
或者使用一种历史悠久的技术,通过记忆来加速这种计算。使用记忆一次后,您可以在更改树时使路径权重值保持最新。
def weight(node):
if node == None:
return 0
node.pathweight=node.val+max(weight(node.left),weight(node.right))
return node.pathweight
def heavy_edge(node):
if not node.left:
lweight=0
else:
lweight=node.left.pathweight
if not node.right:
rweight=0
else:
rweight=node.right.pathweight
if lweight>rweight:
return [node.val,heavy_edge(node.left)]
else:
return [node.val,heavy_edge(node.right)]
weight(t) #Precalculate the pathweight of all the nodes in O(n) time
heavy_edge(T) #Use the precalculated pathweights to efficient find list the heaviest path in O(lg n) time