Блог

Я пытаюсь выполнить задачу leetcode problem # 113, которая заключается в том, что «Учитывая двоичное дерево и сумму, найдите все пути от корня к листу, где сумма каждого пути равна заданной сумме»

Моя проблема в том, почему мой код # 1, показанный ниже, печатает значения всех узлов в дереве? Как работает стек рекурсии в коде # 1 в отличие от того, как работает стек рекурсии в коде # 2, что является правильным решением?

Большое вам спасибо за помощь!

 #code #1
class Solution:
    def pathSum (self, root, sum):
        self.res = []
        self.dfs(root, sum, [])
        return self.res
    def dfs(self, root, sum, path):
        if not root:
            return 
        sum -= root.val
        path  = [root.val]
        if not root.left and not root.right and sum == 0:
            self.res.append(path)
        self.dfs(root.left, sum, path)
        self.dfs(root.right, sum, path)
  

 #code #2
class Solution:
    def pathSum (self, root, sum):
        self.res = []
        self.dfs (root, sum, [])
        return self.res 
    def dfs (self, root, sum, path):
        if not root:
            return 
        sum -= root.val
        if not root.left and not root.right and sum == 0:
            self.res.append(path   [root.val])
        self.dfs(root.left, sum, path [root.val])
        self.dfs(root.right, sum, path [root.val])
  

Что ж, комментарии выше вполне заслуженны, здесь помогли бы несколько примеров. Например, вы говорите о печати, но здесь нет инструкций print, так как же вы управляете этим и как вы это используете?

Сказав это, я подозреваю, что проблема восходит к тому факту, что код # 1 изменяет значение path, в то время как код # 2 этого не делает. Теперь, если бы path был числом, это не имело бы значения, потому что оно передавалось бы по значению. Однако вы передали [] изначально (пустой список), который является объектом . , , поэтому он передается по ссылке. В результате по мере выполнения кода # 1 вы продолжаете изменять узел (путь) над вами, но в коде # 2 переданные пути никогда не меняются.