给定的二进制搜索树和目标值，发现所有的路径（如果存在多于一个），其总和达到目标值。它可以是树中的任何路径。它并不必须是从根

例如，在下面的二进制搜索树

  2
 / \
1 3
 

时的总和应该是6，路径 1 - ＆GT; 2 - ＆GT; 3 应印。

遍历从根的树，做所有的路径和的后序聚会。使用哈希表来存储一个植根于一个节点下去，只可能的路径。我们可以构造经历一个节点的所有路径，从自身和儿童的路径。

下面是psuedo- code表示实现上述，但只存储的数额，而不是实际的路径。对于自己的路径，你需要存储的终端节点的哈希表（我们知道它在哪里开始，并有在树上两个节点之间只有一条路径）。

 函数findsum（树，目标）
  ＃遍历孩子
  如果树形＆GT;左
    findsum（tree.left，目标）
  如果树形＆GT;右
    findsum（tree.right，目标）

  ＃单节点形成一个有效的路径
  tree.sums = {tree.value}

  ＃添加此节点儿童总和
  如果tree.left
    对于left_sum在tree.left.sums
      tree.sums.add（left_sum + tree.value）
  如果tree.right
    对于right_sum在tree.right.sums
      tree.sums.add（right_sum + tree.value）

  ＃难道我们形成的总和？
  如果目标tree.sums
    我们有一个路径

  ＃我们能形成的总和经过该节点和两个孩子？
  如果tree.left和tree.right
    对于left_sum在tree.left.sums
      如果目标 -  left_sum在tree.right.sums
        我们有一个路径

  ＃我们不再需要孩子款项，自由他们的记忆
  如果tree.left
    删除tree.left.sums
  如果tree.right
    删除tree.right.sums
 

此不使用的事实，即树是一个搜索树，所以它可以应用到任何二叉树

有关大树下，哈希表的规模将增长失控。如果只有正值，也可能是更有效地使用由总和索引的数组

Given a binary search tree and a target value, find all the paths (if there exists more than one) which sum up to the target value. It can be any path in the tree. It doesn't have to be from the root.

For example, in the following binary search tree:

  2
 / \ 
1   3 

when the sum should be 6, the path 1 -> 2 -> 3 should be printed.

Traverse through the tree from the root and do a post-order gathering of all path sums. Use a hashtable to store the possible paths rooted at a node and going down-only. We can construct all paths going through a node from itself and its childrens' paths.

Here is psuedo-code that implements the above, but stores only the sums and not the actual paths. For the paths themselves, you need to store the end node in the hashtable (we know where it starts, and there's only one path between two nodes in a tree).

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

This doesn't use the fact that the tree is a search tree, so it can be applied to any binary tree.

For large trees, the size of the hashtable will grow out of hand. If there are only positive values, it could be more efficient to use an array indexed by the sum.