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

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

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

对于大树，哈希表的大小会失控。如果只有正值，使用由总和索引的数组可能更有效。