Обновление переменных в рекурсии - PullRequest
Новая
       39

Обновление переменных в рекурсии

0 голосов
/ 28 апреля 2020

Это относится к этому вопросу кода leetcode: https://leetcode.com/problems/path-sum-iii/

В основном мне дано двоичное дерево, в котором каждый узел содержит целочисленное значение. Я должен найти количество путей, которые суммируются с данным значением.

Построение примера дерева здесь 

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

root = TreeNode(12)
root.left = TreeNode(7)
root.right = TreeNode(1)
root.left.left = TreeNode(4)

root.right.left = TreeNode(10)
root.right.right = TreeNode(5)

Это мое решение с использованием рекурсии 

def count_paths(root, S):

    cache = {0:1}

    def helper(node, S:int, curr_path:int, cache:dict, result:int):

        if not node:
            return result

        curr_path += node.val
        prev_path = curr_path - S

        result += cache.get(prev_path, 0)
        cache[curr_path] = cache.get(curr_path, 0) + 1

        my_node = None
        if node != None:
            my_node = node.val 

        print("node: {}, curr: {}, prev: {}".format(my_node, curr_path, prev_path))                
        print(cache)
        print(result)

        helper(node.left, S, curr_path, cache, result)
        helper(node.right, S, curr_path, cache, result)

        return result

    return helper(root, S, 0, cache, 0)

По сути, я не понимаю, почему рекурсивная функция не обновляет мою переменную result , а обновляет мою переменную cache .

Есть ли правильный путь? обновить переменную результата?

Это контрольный пример 

count_paths(root, 11)

Я напечатал каждую строку результатов 

node: 12, curr: 12, prev: 1
{0: 1, 12: 1}
0
node: 7, curr: 19, prev: 8
{0: 1, 12: 1, 19: 1}
0
node: 4, curr: 23, prev: 12
{0: 1, 12: 1, 19: 1, 23: 1}
1
node: 1, curr: 13, prev: 2
{0: 1, 12: 1, 19: 1, 23: 1, 13: 1}
0
node: 10, curr: 23, prev: 12
{0: 1, 12: 1, 19: 1, 23: 2, 13: 1}
1
node: 5, curr: 18, prev: 7
{0: 1, 12: 1, 19: 1, 23: 2, 13: 1, 18: 1}
0
Tree has paths: 0

Может кто-нибудь объяснить, что Я здесь скучаю? У меня такое чувство, что я совершаю фундаментальную ошибку рекурсии здесь. Я знаю, что создаю класс и просто храню переменную там, но я действительно нахожу, чтобы понять, как правильно выполнять рекурсию. Большое спасибо!

1 Ответ

1 голос
/ 28 апреля 2020

tldr:

Python по умолчанию для передачи по ссылке, но так как целые числа являются неизменяемыми, это похоже на те, которые передаются при копировании. Самый простой обходной путь здесь будет выглядеть примерно так: result += helper(...), or result = helper(...).

Длинный ответ:

Во многих языках (например, C ++ и Java) передача аргументов по умолчанию передает копии этих объектов. Если вы хотите передать объект в функцию и обновить его для использования вне контекста этой функции, вы должны передать указатель (или что-то подобное).

Python, с другой стороны, по умолчанию установлено значение передать по ссылке. Это заставит вас думать, что ваша переменная result будет обновлена ​​на месте, верно?

Проблема в том, что result, будучи целым числом, является неизменным. Таким образом, когда вы изменяете его значение в одном из рекурсивных вызовов, он не меняет переменную result для других вызовов. Он просто переназначает метку result на новое целочисленное значение, , но только в области действия этого вызова функции. Новое значение теряется после возврата из функции.

Если вы хотите обновить целочисленное значение переменной с вызовом функции, вы должны либо установить для переменной возвращаемое значение функции (см. выше tldr), либо обернуть целое число в изменяемый объект (см. Передача целого числа по ссылке в Python * * тысяча двадцать одна). * * тысяча двадцать-дв

...