Как понять следующую рекурсивную функцию в двоичном дереве?

Question

Следующая функция двоичного поиска (корень имеет левый и правый дочерние элементы), которые я не совсем понимаю. В коде он возвращает список, который является самым длинным путем в двоичном дереве. Однако со стороны: 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 

Answer 1

list_longest_path (node.right), несомненно, вернется []. Но как вы, , сравните list_longest_path (2) с []?

Когда встречается рекурсивный вызов типа 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]