Python: как работает список в рекурсии

Question

Я пытаюсь распечатать путь (от корневого до конечного узла) для двоичного дерева.Я пытался использовать список в качестве входных данных, чтобы записать путь и вернуть его.

Однако возвращаемое значение пустое, я вижу, что путь генерируется правильно, печатая путь в функции рекурсии.

Случай 1:

Input:
res = printPath(root, node,[]) 

Output:
res = []

Мой вопрос: как список работает с рекурсией, как Python управляет ее областью действия?

Случай 2:

Input:
p_ = []

res = printPath(root, node, p_)

Output:
res != []

также res не равен окончательному пути, который внутри рекурсии, пожалуйста, дайте мне знать, почему это так.Например, path = [3, 5], res = []

res не пусто, но будет иметь некоторое среднее значение рекурсии.Полагаю, в этом случае список обрабатывается как указатель.

Если вы дадите мне знать разницу между этими двумя случаями, было бы здорово.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def printPath(self, root, node, path):
        if root:
            # print root.val, node
            if root.val == node:
                path.append(node)
                print path
                return path
            if root.left:
                path.append(root.val)
                self.printPath(root.left, node, path)
            if root.right:
                path.append(root.val)
                self.printPath(root.right, node, path)

    def lowest_main(self, root, p):
        # print root.val, p
        p_ = []
        print self.printPath(root, 5, p_)
        # print p_

Answer 1

Случай 1:

Здесь вы передаете объект списка, имеющий ноль элементов, в качестве аргумента для «корневого вызова» printPath().

Внутриэтот вызов, доступ к этому пустому списку можно получить с помощью параметра path.

Во время выполнения функции этот пустой список станет непустым.

Но как только вывышли из этого «корневого вызова» функции, этот параметр с именем path, который ссылается на (теперь непустой) список, выходит из области действия .

Теперь выне осталось никакой другой переменной (или имени), относящейся к этому непустому списку, поэтому у вас нет возможности реально взглянуть на непустой путь и отметить его.

Случай 2:

Здесь также вы передаете пустой объект списка вашему «корневому вызову» printPath().Но разница в том, что еще до того, как вы вызвали printPath(), вы убедились, что есть еще одна переменная (или имя) с именем p_, которая указывает на тот же пустой объект списка, который вы передаете «корневому вызову».,Как и в случае Случай 1 , внутри вызова доступ к пустому объекту списка осуществляется с именем параметра path.Как и в случае Case 1 , этот пустой список станет непустым во время выполнения.Как и в случае Случай 1 , когда корневой вызов в конечном итоге завершает выполнение и возвращает управление, параметр с именем path, который указывал на (теперь не пустой) объект списка, выйдет из области видимости, но выостаются еще с одной переменной p_, указывающей на тот же (теперь не пустой) объект списка.

Причина, по которой print self.printPath(root, 5, p_) печатает None:

Давайте возьмем простое дерево, в котором корневой узел имеет значение 0, а левый дочерний элемент - значение 5. Предположим, что в дереве нет других узлов.

Что происходитв вашем корневом вызове printPath():

Сначала вы проверите if root.val == node.Тест не пройден.

Следующая проверка if root.left.Тест пройдет.Вы введете этот блок if, добавите 0 к пути и сделаете ваш второй вызов printPath().Теперь внимательно обратите внимание на тот факт, что второй вызов сделан из первого вызова.Первый вызов еще не завершен.Фактически, в этот момент как первый, так и второй вызов находятся в состоянии частичного выполнения.Правильный?И первый вызов и второй вызов на два разных номера строки .Первый вызов находится в строке, где printPath() вызывается для левого потомка, а первый вызов вот-вот начнёт выполняться в первой строке printPath().Правильно?

Что будет дальше?

Второй вызов также проверяет if root.val == node.На этот раз тест проходит успешно, и он входит в блок if, добавляет 5 к path и возвращает path.

Но куда же возвращается это возвращаемое значение?К месту, где произошел этот второй вызов!Который, если вы помните, это еще одна строка в printPath().В этой строке вы вызываете printPath(), но не захватываете его возвращаемое значение ни в одной переменной - вы просто игнорируете его возвращаемое значение.Таким образом, строка 0 5, возвращаемая вторым вызовом, игнорируется.Выполнение первого вызова продолжается до тех пор, пока оно не достигнет последней строки printPath().В последней строке нет другого оператора return.Таким образом, при отсутствии явного оператора return любая функция Python вернет None.Таким образом, этот первый вызов вернет None к месту, где произошел ваш первый вызов (я думаю, это в lowest_main()).

Первый вызов печатает это значение None.

Как исправить:

Чтобы исправить это, измените следующую строку:

self.printPath(root.left, node, path)

на эту:

return self.printPath(root.left, node, path)

Аналогично, измените следующую строку:

self.printPath(root.right, node, path)

на эту:

return self.printPath(root.right, node, path)

Answer 2

Потому что:

>>> [].append(2)
>>> []
[]
>>> l=[]
>>> l.append(2)
>>> l
[2]
>>> 

Поскольку [] нигде не хранится, поэтому не будет обновлять никакие переменные, поэтому.

[] будет храниться в памяти послеappend, но нет доступа к нему.