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

Z时代
2024-01-10
分类：问答

给定一个二叉搜索树和一个目标值，找到所有合计为目标值的路径（如果存在多个路径）。它可以是树中的任何路径。它不必从根本上讲。

例如，在以下二进制搜索树中：

2 / \ 1 3

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

回答：

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

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

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