如何理解二叉樹中的以下遞歸函數？

以下是一個二元搜索函數（一個根有一個左邊和一個右邊的孩子），我不太明白。在代碼中，它返回一個列表，該列表是二叉樹中最長的路徑。但是對於零件： return_path_left = list_longest_path(node.left) return_path_right = list_longest_path(node.right) if len(return_path_left) > len(return_path_right):如何理解二叉樹中的以下遞歸函數？

如何比較兩個遞歸調用？例如，如果樹是

1 /\ 2 list_longest_path(node.right)肯定會返回[]。但是，您如何將list_longest_path(2)與[]進行比較？

有人幫助會很好。

def list_longest_path(node): 
    """ 
    List the data in a longest path of node. 

    @param BinaryTree|None node: tree to list longest path of 
    @rtype: list[object] 

    >>> list_longest_path(None) 
    [] 
    >>> list_longest_path(BinaryTree(5)) 
    [5] 
    >>> b1 = BinaryTree(7) 
    >>> b2 = BinaryTree(3, BinaryTree(2), None) 
    >>> b3 = BinaryTree(5, b2, b1) 
    >>> list_longest_path(b3) 
    [5, 3, 2] 
    """ 
    if node is None: 
     return [] 
    else: 
     return_path_left = list_longest_path(node.left) 
     return_path_right = list_longest_path(node.right) 
     if len(return_path_left) > len(return_path_right): 
      return [node.data] + return_path_left 
     else: 
      return [node.data] + return_path_right

來源

2016-04-23 1412

list_longest_path（node.right）必要回到[]。但你怎麼比較list_longest_path（2）與[]？

當遇到類似list_longest_path（2）的遞歸調用時，它會被壓入調用堆棧。由於調用堆棧是一個堆棧[因此是先進先出]，當前堆棧幀將暫停，並且將評估list_longest_path（2）。

list_longest_path（2）進行評價，如下所示：

作爲左和右節點是無，return_path_left = []; return_path_right = [];因此，list_longest_path（2）= [2] + [] = [2]

然後，list_longest_path（2）stackframe從堆棧中彈出，程序在前一個堆棧幀中恢復執行。我們現在有一個簡單的值list_longest_path（2）= [2] 然後我們完成這個函數len（[2]）> len（[]）的執行，所以list_longest_path（1）= [1] + [2] = [1,2]

來源

2016-04-23 03:36:28 gnicholas

如何理解二叉樹中的以下遞歸函數？

回答

相關問題