给定一棵二叉树和一个数字“S”，找出树中所有路径，使得每条路径的所有节点值之和等于“S”。请注意，路径可以在任何节点开始或结束，但所有路径必须遵循从父节点到子节点（从上到下）的方向。

这是我找到的答案，我确实理解它是如何工作的，但我最初想到的是我想要实施的不同的东西，我很难弄清楚。

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


def count_paths(root,S):
  return count_paths_recursive(root,S,[])


def count_paths_recursive(currentNode,currentPath):
  if currentNode is None:
    return 0

  # add the current node to the path
  currentPath.append(currentNode.val)
  pathCount,pathSum = 0,0
  # find the sums of all sub-paths in the current path list
  for i in range(len(currentPath)-1,-1,-1):
    pathSum += currentPath[i]
    # if the sum of any sub-path is equal to 'S' we increment our path count.
    if pathSum == S:
      pathCount += 1

  # traverse the left sub-tree
  pathCount += count_paths_recursive(currentNode.left,currentPath)
  # traverse the right sub-tree
  pathCount += count_paths_recursive(currentNode.right,currentPath)

  # 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]

  return pathCount


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)
  print("Tree has paths: " + str(count_paths(root,11)))


main()

我想要的是做 DFS，但不是保留一个列表，我只想跟踪我当前的节点并有一个起始节点以及我保留在内存中例如，

对于树...

                 1
                / \    
               7   9
              / \  |\
             6   5 2 3

如果我想找到所有加起来为 12 的路径并且不必从根开始或从叶子结束，那么我的计划是跟踪我的初始起始节点和我所在的当前节点。

为了保持这篇文章简短，我跳过了第一条路径

1 -> 7
1 -> 7 -> 6
7 -> 6

加起来为 12。

从下一个可能的路径开始让我们从根节点开始......

我们在 1 并且 1 小于 12 所以我们继续下一个节点 7 并且 1 + 7 是 8 并且 8 小于 12 所以我们继续到下一个节点 5 并且 8 + 5 是 13。

13 大于 12 我立即知道我需要从头开始收缩路径，在这种情况下，节点值为 1。收缩时，我们需要确保从运行总和中减去我们得到的值我们正在放手的节点。所以 13 - 1 是 12，我们找到了一条路径，它加起来就是目标总和。对其余的路径一遍又一遍地继续这个算法

class TreeNode:
  def __init__(self,S):
  return count_paths_helper(root,root,0)

def count_paths_helper(current_node,start,running_sum,num_paths):
  if current_node is None:
    return 0

  running_sum += current_node.val

  # Found a path
  if running_sum == S:
    return 1
  
  # shrink the path starting from the beginning
  if running_sum > S:
    # if the beginning of the path is also equal to the end of the path continue on our path
    # and get rid of the running sum we currently have
    if start == current_node:
      num_paths += count_paths_helper(current_node.left,running_sum - start.val,num_paths)
      num_paths += count_paths_helper(current_node.right,num_paths)
    # shrink the path starting from the beginning moving to the left
    if start.left:
      num_paths += count_paths_helper(current_node,start.left,num_paths)
    # shrink the path starting from the beginning moving to the right
    if start.right:
      num_paths += count_paths_helper(current_node,start.right,num_paths)
  # if we are on a path that has not exceeded the target and not equal to the target sum
  # continue on our path
  else:
    num_paths += count_paths_helper(current_node.left,num_paths)
    num_paths += count_paths_helper(current_node.right,num_paths)

  return num_paths

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)
  print("Tree has paths: " + str(count_paths(root,11)))


main()

这行不通，我只是不明白如何实现这一点。