查找二叉樹中最重的路徑有效 - 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 

因此，給定一棵像[[無a 7無] b 5 [[無c 8無] d 3無]]的樹]：

>>> weight(t) 
16 
>>> heavy_path(t) 
[5, 3, 8] 

這樣做會更好嗎？

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) 

或使用歷史悠久的技術，通過Memoization加快這種計算。一旦你使用了memoization一次，你可以保持pathweight值是最新的，因爲你改變了你的樹。

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