从根开始在二叉树中查找路径以留下总和，s 没有按我预期的那样工作

Question

我正在寻找

Tree paths with required_sum 23: [[12, 7, 4], [12, 1, 10]]

但我得到的是

Tree paths with required_sum 23: [[], []]

我的代码如下...

def findPaths(root, val):
  allPaths = []
  findPathsHelper(root, sum, [], allPaths)
  return allPaths

def findPathsHelper(currentNode, sum, currentPath, allPaths):
  if currentNode is None:
    return

  currentPath.append(currentNode.val)
  
  if currentNode.val == sum and currentNode.left is None and currentNode.right is None:
    allPaths.append(currentPath)
  else:
    findPathsHelper(currentNode.left, sum - currentNode.val, currentPath, allPaths)
    findPathsHelper(currentNode.right, sum - currentNode.val, currentPath, allPaths)
 
  del currentPath[-1]

如果我将 allPaths.append(currentPath) 所在的行更改为 allPaths.append(list(currentPath))，我会得到正确答案，但我不知道为什么。

如果我有以下...

l1 = []
l2 = [1, 2, 3]
l1.append(l2)
l1.append(l2)

# then l1 == [[1, 2, 3], [1, 2, 3]]

如果我改为这样做...

l1 = []
l2 = [1, 2, 3]
l1.append(list(l2))
l1.append(list(l2))

# then l1 == [[1, 2, 3], [1, 2, 3]]

在这种情况下两者是相同的，所以我不知道为什么在我的代码中它不 return 正确的东西

Answer 1

我认为你的问题是你在复制之前删除了当前路径项。 Python 列表是“按对象引用传递”

del currentPath[-1]

还应该使用 findPathsHelper(root, val, []) 而不是 findPathsHelper(root, sum, [], allPaths) 你没有传递值。

为了测试，我创建了一个演示项目并使用了一个全局变量，看起来它正在运行。

class Node(object):
    def __init__(self, value,left=None, right=None):
        self.val = value
        self.left = left
        self.right = right

    def __str__(self):
        return '{:d} {:d}'.format(self.value)
allPaths=[]
def findPaths(root, val):
    global allPaths
    allPaths=[]
    findPathsHelper(root, val, [])
    return allPaths

def findPathsHelper(currentNode, sum, currentPath):
    if currentNode is None:
        return

    currentPath.append(currentNode.val)
    
    if currentNode.val == sum and currentNode.left is None and currentNode.right is None:
        global allPaths
        allPaths.append(currentPath.copy())
    else:
        findPathsHelper(currentNode.left, sum - currentNode.val, currentPath)
        findPathsHelper(currentNode.right, sum - currentNode.val, currentPath)
    
    del currentPath[-1]

if __name__ == "__main__":
    root=Node(12,Node(7,Node(4),Node(10)),Node(1,Node(9),Node(10)))
    result=findPaths(root,23)
    print(allPaths)

从根开始在二叉树中查找路径以留下总和，s 没有按我预期的那样工作

Find paths in a binary tree from root to leave what sum, s not working as I expected

python

algorithm

binary-tree

depth-first-search

python-3.x