给定一棵二叉树和一个数字“S”，找到从根到叶的所有路径，使得每条路径的所有节点值的总和等于“S”

Question

下面的示例来自在线资源，我不确定为什么我们需要向 allPaths 添加 currentPath 的新副本。我认为在我们通过 del currentPath[-1] 返回递归调用堆栈时删除最后一个元素确保我们没有将以前的路径添加到新路径

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


def find_paths(root, required_sum):
  allPaths = []
  find_paths_recursive(root, required_sum, [], allPaths)
  return allPaths


def find_paths_recursive(currentNode, required_sum, currentPath, allPaths):
  if currentNode is None:
    return

  # add the current node to the path
  currentPath.append(currentNode.val)

  # if the current node is a leaf and its value is equal to required_sum, save the current path
  if currentNode.val == required_sum and currentNode.left is None and currentNode.right is None:
    allPaths.append(list(currentPath))
  else:
    # traverse the left sub-tree
    find_paths_recursive(currentNode.left, required_sum -
                         currentNode.val, currentPath, allPaths)
    # traverse the right sub-tree
    find_paths_recursive(currentNode.right, required_sum -
                         currentNode.val, currentPath, allPaths)

  # remove the current node from the path to backtrack,
  # we need to remove the current node while we are going up the recursive call stack.
  del currentPath[-1]


def main():

  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)
  required_sum = 23
  print("Tree paths with required_sum " + str(required_sum) +
        ": " + str(find_paths(root, required_sum)))


main()

Answer 1

find_paths_recursive 函数的设计使得附加到 allPaths 是 return 将结果发送给调用者的方式。

def find_paths(root, required_sum):
  allPaths = []
  find_paths_recursive(root, required_sum, [], allPaths)
  return allPaths

这里在 find_paths 中，allPaths 作为一个空列表传递给 find_paths_recursive 完成后，它将包含结果（从根到叶的路径满足描述的条件）。

Answer 2

重要的是要意识到在整个过程中只有一个 currentPath 列表。它是在初始调用中创建的：

find_paths_recursive(root, required_sum, [], allPaths)
#                                        ^^---here!

该单个列表发生的所有事情是将元素附加到它，然后再次从中删除（回溯时）。它不断地增长和收缩，增长和收缩，……在它的整个生命周期中。但它是相同的，单个列表实例。

如果您不复制就将该列表附加到 allPaths，即像这样：

allPaths.append(currentPath)

...然后意识到虽然该列表是 allPaths 的成员，但它将被未来的 append 和 [=17= 】动作就可以了！甚至更多：由于稍后再次执行上述语句：

allPaths.append(currentPath)

... 完全 追加了 allPaths 中已有的 列表... 因为只有一个 currentPath 列表！因此，您最终会 allPaths 重复引用同一个列表。

结论：获取currentPath的副本很重要，它不会再被currentPath上的未来突变所改变。这就像拍摄 currentPath.

的当前状态的快照

Answer 3

我建议将问题分解成不同的部分。首先我们写一个通用的 paths 函数 -

def paths (t = None, p = ()):
  if not t:
    return
  elif t.left or t.right:
    yield from paths(t.left, (*p, t.val))
    yield from paths(t.right, (*p, t.val))
  else:
    yield (*p, t.val)

mytree = TreeNode \
  ( 12
  , TreeNode(7, TreeNode(4))
  , TreeNode(1, TreeNode(10)) 
  )

现在我们可以看到 paths 是如何工作的 -

for p in paths(mytree):
  print(p)

(12, 7, 4)
(12, 1, 10)

现在我们可以编写 solver 专门化 paths -

def solver (t = None, q = 0):
  for p in paths(t):
    if sum(p) == q:
      yield p

solver 是一个产生所有可能解决方案的生成器。对于这样的程序来说，这是一个不错的选择，因为您可以 pause/cancel 在找到您正在寻找的解决方案后立即解决 -

for sln in solver(mytree, 23):
  print(sln)

输出不是特别有趣，因为 mytree 中的每个分支总和为 23 -

(12, 7, 4)
(12, 1, 10)

如果我们使 anothertree 具有不同的值，我们可以看到更有趣的输出 -

anothertree = TreeNode \
  ( 1
  , TreeNode(7, TreeNode(4), TreeNode(5))
  , TreeNode(9, TreeNode(2), TreeNode(7))
  )

for sln in solver(anothertree, 12):
  print(sln)

(1, 7, 4)
(1, 9, 2)

给定一棵二叉树和一个数字“S”，找到从根到叶的所有路径，使得每条路径的所有节点值的总和等于“S”

Given a binary tree and a number ‘S’, find all paths from root-to-leaf such that the sum of all the node values of each path equals ‘S’

python

list

recursion

depth-first-search