3

我正在尝试解决以下问题：查找树中最重节点的权重，并将该节点表示为列表。这是我想出的，但我很确定这是一个非常混乱的解决方案。关于在给定课程的框架内更有效地做这件事的任何建议？

给定班级：

    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]

有什么更好的方法来做到这一点？

4

1 回答 1

2

假设您将最重路径解释为始终从树的根开始并下降到单个叶子的路径。您可以尝试合并权重查找和路径构建操作：

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
于 2013-12-21T16:14:31.727 回答