Почему этот предварительный обход возвращает последние узлы?

Question

Я понимаю, почему буквы [A, B, D] добавляются в список. Но я не понимаю, как добавляются последние две буквы [E, C]. После pre_order («C», узлы) буква «C» не имеет левого потомка, как функция может узнать, что она прошла один шаг до буквы «B» и проверила свои дочерние элементы, и так далее? Смотрите изображение дерева: дерево

def pre_order(root, nodes):
    nodes.append(root.data)
    if root and root.left:
        pre_order(root.left, nodes)
    if root and root.right:
        pre_order(root.right, nodes)
    return nodes

    print(pre_order(root, [])) #prints ['A', 'B', 'D', 'E', 'C']

Answer 1

После выполнения функция возвращается в любое место, где ее называют, в данном случае - к вызову той же функции, но с другими аргументами.

Давайте посмотрим, как это работает в вашем примере.Каждый отступ является новым исполнением - посмотрите, как мы возвращаемся к предыдущему отступу и продолжаем.

• мы начинаем с pre_order на узле A с пустым списком
  • добавляем A в текущий список,новый список = [A]
  • первые if хиты, поэтому мы выполняем на B со списком:
    • добавляем B к текущему списку [A], новый список = [A, B]
    • первые if попадания, поэтому мы выполняем на D список:
      • добавляем D в текущий список [A, B], новый список = [A, B, D]
      • первый if не бьет, потому что у D нет левого ребенка
      • второй if не бьет, потому что у D нет правого ребенка
      • return [A, B, D]
    • мы получили результат внутреннего выполнения и продолжим там, где он был запущен (в B)
    • секунда ifХиты, поэтому мы выполняем на E со списком (теперь изменился во внутренней функции, благодаря изменчивости)
      • добавить E к текущему списку [A, B, D], новый список = [A, B,D, E]
      • первый if не чэто потому что E не имеет левого потомка
      • секунда if не бьет, потому что у E нет правого потомка
      • return [A, B, D, E]
    • мы получили результат внутреннего выполнения и продолжим там, где он был запущен (в B)
    • return [A, B, D, E]
  • мы получили результат внутреннего выполнения и продолжаем там, где он был запущен (в A)
  • секунд if попаданий, поэтому мы выполняем на C со списком (теперь менялись несколько разво внутренних исполнениях)
    • добавить C к текущему списку [A, B, D, E], новый список = [A, B, D, E, C]
    • первый ifне срабатывает, потому что у C нет левого потомка
    • секунда if не срабатывает, потому что у C нет правого потомка
    • return [A, B, D,E, C]
  • мы получили результат внутреннего выполнения и продолжим там, где он был запущен (в A)
  • return [A, B, D, E,C]
• мы возвращаемся туда, где мы впервые выполнили pre_order - то естьфункция печати

[Могут быть небольшие опечатки и небольшие ошибки в списке, я скопировал большинство вещей, и, возможно, я забыл об изменении чего-либо]