Skip to main content
 首页 » 编程设计

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

2025年04月02日17sky-heaven

以下是我不太理解的二进制搜索函数(一个根有一个左 child 和一个右 child )。在代码中,它返回一个列表,该列表是二叉树中最长的路径。但是对于部分: return_path_left = list_longest_path(node.left) return_path_right = list_longest_path(node.right) 如果 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 

请您参考如下方法:

list_longest_path(node.right) will surely return []. But how do you compare list_longest_path(2) with []?

当遇到像 list_longest_path(2) 这样的递归调用时,它会被压入调用堆栈。由于调用堆栈是一个堆栈[因此是后进先出],当前堆栈帧被暂停并评估 list_longest_path(2) 。

list_longest_path(2) 的计算方式如下:

由于左右节点均为None,return_path_left = []; return_path_right = [];所以 list_longest_path(2) = [2] + [] = [2]

然后 list_longest_path(2) 堆栈帧被弹出堆栈,程序在前一个堆栈帧中恢复执行。我们现在有一个简单的值 list_longest_path(2) = [2] 然后我们完成这个函数的执行 len([2]) > len([]) 所以 list_longest_path(1) = [1] + [2] = [1,2]