Python: почему содержимое списка отличается внутри и снаружи функции?

Question

У меня есть функция, выполняющая обход двоичного дерева, и у меня есть глобальный список «стек» для хранения временных значений.

stack = []

def search(root, v):
    global stack
    stack.append(root.info)    
    if root.info == v:
        print(stack) #<------- THE FIRST PRINT IS HERE
        return
    if root.left is not None:
        search(root.left, v)
    if root.right is not None:
        search(root.right, v)
    stack.pop()
    pass

def lca(root, v1, v2):
    search(root,v1)
    print(stack) #<------- THE SECOND PRINT IS HERE

Ваш вывод (стандартный вывод)

[4, 2, 1]
[4]

вход: v1 = 1, v2 = 7

Когда я печатаю значение списка изнутри и снаружи функции, я обнаружил, что результатыотличается - при печати внутри получается [4,2,1], а снаружи - [4].Я пробовал разные способы, такие как создание списка вне функции, а затем передать его в функцию, результат всегда одинаков.Может кто-нибудь знает, почему это произошло?

Answer 1

Кажется, вы верите, что после того, как вы нажали явное return в вашей функции search, ваш рекурсивный поиск прекращается.Но это не так.Вызовы search выше стека вызовов по-прежнему будут запускать дополнительные поиски, отбрасывая вещи stack, изменяя его содержимое.

Возможно, вы хотите что-то вроде этого: используйте возвращаемое значение для подачи сигнала от search когда он успешно обнаружил искомую вещь и больше не ищет после этого.

def search(root, v):
    global stack
    stack.append(root.info)    
    if root.info == v:
        print(stack)
        return True
    if root.left is not None and search(root.left, v):
        return True
    if root.right is not None and search(root.right, v):
        return True
    stack.pop()
    return False

Это предотвратит изменение стека после точки, в которой было найдено значение.