Найти самый тяжелый путь в двоичном древе эффективно - 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] 

Что было бы лучшим способом сделать это?

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. После того, как вы один раз воспользовались записью, вы можете просто обновлять значения весового значения при изменении дерева.

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