Присвоение значения переменной Python в рекурсии

Question

Существует два решения проблемы:

Проблема:

Введите корневой узел двоичного дерева и целое число, чтобы вывести путь, в котором сумма значений узла вдвоичное дерево является входным целым числом.Путь определяется как путь от корневого узла дерева до следующего узла, пока не пройдет конечный узел.(Примечание: в списке возвращаемых значений массив с наибольшей длиной массива находится впереди)

решение одно

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def FindPath(self, root, expectNumber):
        if not root:
            return []
        result=[]
        path=[root]
        path_sum=0
        def find(root,path,path_sum):
            isleaf= root.left==None and root.right==None  # a bool,whether is leaf node

            path_sum+=root.val
            if isleaf and path_sum==expectNumber:
                t=[]
                for i in path:
                    t.append(i.val)
                result.append(t) # add a appropriate path's value to result
            if path_sum<expectNumber:
                if root.left:

                    find(root.left,path+[root.left],path_sum)#note!!!!!
                if root.right:

                    find(root.right,path+[root.right],path_sum)#note!!!!!

        find(root,path,path_sum)
        return result

решение 2

class Solution:
    def FindPath(self, root, expectNumber):
        if not root:
            return []
        result=[]
        path=[]
        path_sum=0
        def find(root,path,path_sum):
            isleaf= root.left==None and root.right==None
            path.append(root)#note!!!!!
            path_sum+=root.val
            if isleaf and path_sum==expectNumber:
                t=[]
                for i in path:
                    t.append(i.val)
                result.append(t)
            if path_sum<expectNumber:
                if root.left:
                    find(root.left,path,path_sum)
                if root.right:
                    find(root.right,path,path_sum)
            path.pop()#note!!!!!
        find(root,path,path_sum)
        return result

ДонНе знаю, почему в решении 1 список путей не нуждается в операции pop, а в решении 2.Другими словами, почему решение 1 не разделяет список путей, а решение 2 делает это.

Пожалуйста, помогите мне, я не могу найти такую ​​статью, чтобы понять меня!

Моя точка зрения не таковао классе, вы также можете использовать функцию для решения этой проблемы.

Меня волнует Python присвоение значения переменной в рекурсии !!!

Answer 1

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

class Solution:
  @classmethod
  def find_path(cls, head, val:int, current = []):
    if sum(current) == val:
       yield current
    elif head.value+sum(current) < val:
      if head.left is not None:
        yield from cls.find_path(head.left, val, current+[head.value])
      if head.right is not None:
        yield from cls.find_path(head.right, val, current+[head.value])
    elif head.value+sum(current) == val:
      yield current+[head.value]

---

Класс дерева для демонстрации:

class Tree:
  def __init__(self, **kwargs):
    self.__dict__ = {i:kwargs.get(i) for i in ['left', 'right', 'value']}

t = Tree(value=10, left=Tree(value=8, left=Tree(value=3), right=Tree(value=5)), right=Tree(value=2, left=Tree(value=2)))

""" 
     10
   /    \
  8      2
 / \    /
3   5  2
"""
results = [list(Solution.find_path(t, i)) for i in [12, 14, 23]]

Вывод:

[[[10, 2]], [[10, 2, 2]], [[10, 8, 5]]]

Answer 2

Я считаю, что в вашем коде много ошибок, из-за которых будет сложно отследить:

**** Во-первых: любое определение или функция внутри любого класса Python должны быть в нижнем регистре с подчеркиванием, чтобы мы могли выяснить, что такое класс из функции, поэтому ваш FindPath () должен быть >>>>>> find_path ()

**** Второе: если вы хотите объявить какие-либо аргументы глобальной области видимости класса, вы должны сделать это внутри функции как конструктор или инициализатор, поэтому ваш код для E.G должен быть:

class Solution:
    def __init__(self, root, expect_number):
        self.root = root
        self.expect_number = expect_number

и каждый раз, когда вы будете вызывать любой аргумент внутри класса, вы должны вызывать его с помощью (self.arg), например, self.root

**** Третье: эта строка вообще не понятна:

def find(root,path,path_sum):
            isleaf= root.left==None and root.right==None

это совершенно неверно: вы присваиваете isleaf значение None заранее заданному значению, и вы снова присваиваете переменной isleaf слово (и) так, в качестве логической или питонической логики: как будет понимать isleaf, чтобы получить два Значения (root.left и root.right), которые получают значения None, не имеют никакого смысла. поэтому, пожалуйста, дайте нам представление о том, что именно вы хотите сделать здесь.

**** Четвертое: рассмотрим один пробел после и перед любым оператором, вместо "если путь_сумма

**** Не бойтесь давать переменным или аргументам реальные имена, чтобы различать реальные потребности в них, или, по крайней мере, пытаться дать комментарий к ним, например: что делает t = [] !!!!!!!

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

---

Новое редактирование:

В решении № 2: каждый раз, когда вы вызываете функцию find (), вы добавляете или добавляете значение 'root' в список путей

    def find(root,path,path_sum):
        isleaf= root.left==None and root.right==None
        path.append(root) # here you added the root to the path

и код все еще рекурсивный, пока это условие не станет ложным:

if path_sum<expectNumber: 

и когда оно ложно, он начнет вызывать метод pop (), который удалит последний «корень», добавленный в список путей:

path.pop()

и затем он вызывает следующую строку, которая снова вызовет функцию поиска

find(root,path,path_sum)

но на этот раз он будет вызываться с пустым значением пути, ПОЧЕМУ? потому что первый объект списка путей "path = []" находится на том же уровне области, что и вызов последней функции поиска "find (root, path, path_sum)" таким образом, аргумент внутреннего пути и его значения не видны областью внешнего пути, они видны только функцией find () самостоятельно.

И эта область выдает то же самое для «Решения 1», за исключением того, что вы передаете список путей с корневым значением, и когда это условие ложно

if path_sum<expectNumber:

код снова вызовет функцию find (), но путь будет иметь только корневое значение в первом объявлении "path = [root]".

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