在二叉树中高效地找到最重的路径 - Python

Question

我试图解决以下问题：找到树中最重节点的权重，并将该节点表示为列表。这是我想出的解决方案，但我相当确定它是一个非常混乱的解决方案。在给定的类框架内更有效地处理它的任何建议吗？

给定类：

    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]

有什么更好的方法来做这件事吗？

- nanachan

---

考虑在Code Review上提出这个问题。 - Maciej Gol

看起来 heavy_path() 应该被递归调用，但我没有看到递归。 - Richard

Answer 1

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

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

- Richard