如何理解二叉树中的以下递归函数？

以下是一个二元搜索函数（一个根有一个左边和一个右边的孩子），我不太明白。在代码中，它返回一个列表，该列表是二叉树中最长的路径。但是对于零件： 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

如何理解二叉树中的以下递归函数？

回答

相关问题