在二叉搜索树中查找求和目标值的路径

Question

给定二叉搜索树和目标值,找到总计达目标值的所有路径(如果存在多个路径).它可以是树中的任何路径.它不必来自根.

例如,在以下二叉搜索树中:

  2
 / \ 
1   3 

当总和应为6时,1 -> 2 -> 3应打印路径.

Answer 1

从根遍历树并执行所有路径和的后序收集.使用哈希表来存储以节点为根的可能路径并向下运行.我们可以构建从自身及其子路径经过节点的所有路径.

这是实现上述的伪代码,但只存储总和而不是实际路径.对于路径本身,您需要将末端节点存储在哈希表中(我们知道它在哪里开始,并且树中的两个节点之间只有一条路径).

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

这不使用树是搜索树的事实,因此它可以应用于任何二叉树.

对于大型树木,哈希表的大小将无法实现.如果只有正值,则使用由sum求索的数组可能更有效.

Answer 2

我的回答是O(n^2),但我认为它是准确的,采用略有不同的方法,看起来更容易实现.

假设存储在节点的值i由表示VALUE[i].我的想法是在每个节点上存储从root该节点到路径的值的总和.因此,对于每个节点i,SUM[i]是从root节点到节点的路径的总和i.

然后,对于每个节点对(i,j),找到它们的共同祖先k.如果SUM(i)+SUM(j)-SUM(k) = TARGET_SUM,你找到了答案.

这是O(n^2)因为我们循环遍历所有节点对.虽然,我希望我能找到比挑选所有对更好的方法.

我们可以通过丢弃根据子树value的节点大于的子树来优化它TARGET_SUM.欢迎任何进一步的优化:)

伪代码:

# Skipping code for storing sum of values from root to each node i in SUM[i]
for i in nodes:
    for j in nodes:
        k = common_ancestor(i,j)
        if ( SUM[i] + SUM[j] - SUM[k] == TARGET_SUM ):
            print_path(i,k,j)

common_ancestor对于二叉搜索树,函数是一个非常标准的问题.Psuedocode(来自内存,希望没有错误!):

sub common_ancestor (i, j):
  parent_i = parent(i)
  # Go up the parent chain until parent's value is out of the range. 
  # That's a red flag.
  while( VAL[i] <= VAL[parent_i] <= VAL[j] ) : 
    last_parent = parent_i
    parent_i = parent(i)
    if ( parent_i == NULL ): # root node
      break
return last_parent