从根开始遍历树，然后对所有路径和求和。使用哈希表存储可能的路径，该路径以节点为根并且仅向下运行。我们可以构造从节点及其子路径通过节点的所有路径。

这是实现上述内容的伪代码，但仅存储总和而不存储实际路径。对于路径本身，您需要将结束节点存储在哈希表中（我们知道它的开始位置，并且树中两个节点之间只有一条路径）。

function findsum(tree, target)
  # Traverse the children
  if tree->left
    findsum(tree.left, target)
  if tree->right
    findsum(tree.right, target)

  # Single node forms a valid path
  tree.sums = {tree.value}

  # Add this node to sums of children
  if tree.left
    for left_sum in tree.left.sums
      tree.sums.add(left_sum + tree.value)
  if tree.right
    for right_sum in tree.right.sums
      tree.sums.add(right_sum + tree.value)

  # Have we formed the sum?
  if target in tree.sums
    we have a path

  # Can we form the sum going through this node and both children?
  if tree.left and tree.right
    for left_sum in tree.left.sums
      if target - left_sum in tree.right.sums
        we have a path

  # We no longer need children sums, free their memory
  if tree.left
    delete tree.left.sums
  if tree.right
    delete tree.right.sums

这没有使用树是搜索树的事实，因此可以将其应用于任何二叉树。

对于大树，哈希表的大小将无法控制。如果只有正值，则使用以总和索引的数组可能会更有效。