查找BST中的路径上是否存在给定的总和

Question

问题是找出BST中任何路径上是否存在给定的总和.如果路径意味着根到叶子,那么这个问题很容易,或者如果路径意味着从根到叶子的路径的一部分可能不包括根或叶子,则该问题很容易.但这里变得困难,因为路径可能跨越节点的左右子节点.例如,在给定的图中,在圆圈路径上存在132的总和.我怎样才能找到这样一条路径的存在？使用散列来存储节点下的所有可能的总和是不受欢迎的!

Answer 1

您当然可以生成所有可能的路径，并在进行过程中逐步求和。该树是 BST 的事实可能会让您通过限制某些总和来节省时间，尽管我不确定这是否会带来渐近速度的增加。问题在于，使用给定节点的左子节点形成的总和不一定小于使用右子节点形成的总和，因为前一个总和的路径可能包含更多节点。以下算法适用于所有树，而不仅仅是 BST。

要生成所有可能的路径，请注意路径的最高点是特殊的：它是路径中唯一允许（尽管不是必需）将两个子路径都包含在路径中的点。每条路径都包含一个唯一的最高点。因此外层递归应该是访问每一个树节点，并生成以该节点为最顶层的所有路径。

// Report whether any path whose topmost node is t sums to target.
// Recurses to examine every node under t.
EnumerateTopmost(Tree t, int target) {
    // Get a list of sums for paths containing the left child.
    // Include a 0 at the start to account for a "zero-length path" that
    // does not contain any children.  This will be in increasing order.
    a = append(0, EnumerateSums(t.left))
    // Do the same for paths containing the right child.  This needs to
    // be sorted in decreasing order.
    b = reverse(append(0, EnumerateSums(t.right)))

    // "List match" to detect any pair of sums that works.
    // This is a linear-time algorithm that takes two sorted lists --
    // one increasing, the other decreasing -- and detects whether there is
    // any pair of elements (one from the first list, the other from the
    // second) that sum to a given value.  Starting at the beginning of
    // each list, we compute the current sum, and proceed to strike out any
    // elements that we know cannot be part of a satisfying pair.
    // If the sum of a[i] and b[j] is too small, then we know that a[i]
    // cannot be part of any satisfying pair, since all remaining elements
    // from b that it could be added to are at least as small as b[j], so we
    // can strike it out (which we do by advancing i by 1).  Similarly if
    // the sum of a[i] and b[j] is too big, then we know that b[j] cannot
    // be part of any satisfying pair, since all remaining elements from a
    // that b[j] could be added to are at least as big as a[i], so we can
    // strike it out (which we do by advancing j by 1).  If we get to the
    // end of either list without finding the right sum, there can be
    // no satisfying pair.
    i = 0
    j = 0
    while (i < length(a) and j < length(b)) {
        if (a[i] + b[j] + t.value < target) {
            i = i + 1
        } else if (a[i] + b[j] + t.value > target) {
            j = j + 1
        } else {
            print "Found!  Topmost node=", t
            return
        }
    }

    // Recurse to examine the rest of the tree.
    EnumerateTopmost(t.left)
    EnumerateTopmost(t.right)
}

// Return a list of all sums that contain t and at most one of its children,
// in increasing order.
EnumerateSums(Tree t) {
    If (t == NULL) {
        // We have been called with the "child" of a leaf node.
        return []     // Empty list
    } else {
        // Include a 0 in one of the child sum lists to stand for
        // "just node t" (arbitrarily picking left here).
        // Note that even if t is a leaf node, we still call ourselves on
        // its "children" here -- in C/C++, a special "NULL" value represents
        // these nonexistent children.
        a = append(0, EnumerateSums(t.left))
        b = EnumerateSums(t.right)
        Add t.value to each element in a
        Add t.value to each element in b
        // "Ordinary" list merge that simply combines two sorted lists
        // to produce a new sorted list, in linear time.
        c = ListMerge(a, b)
        return c
    }
}

上面的伪代码仅报告路径中最顶层的节点。可以通过EnumerateSums()返回对列表(sum, goesLeft)而不是简单的和列表来重建整个路径，其中goesLeft是一个布尔值，指示用于生成该和的路径最初是否从父节点向左走。

上面的伪代码为每个节点多次计算总和列表：除了为自身调用之外，EnumerateSums(t)还将为树中上面的每个节点调用一次。可以记住每个节点的和列表，以便在后续调用时不会重新计算它，但实际上这并不能改善渐进性：使用以下方法生成 n 个和的列表只需要 O(n) 工作：简单的递归，并将其更改为 O(1) 不会改变总体时间复杂度，因为任何调用生成的整个总和列表通常都必须由调用者读取，而这需要 O(n) 时间。编辑：正如 Evgeny Kluev 所指出的，实际上表现得像合并排序，当树完全平衡时为 O(nlog n)，当树是单路径时为 O(n^2)。因此，记忆实际上会带来渐近的性能改进。ttEnumerateSums()EnumerateSums() EnumerateSums()

可以通过重新排列成EnumerateSums()一个类似迭代器的对象来摆脱临时总和列表，该对象延迟执行列表合并，并且可以查询以按升序检索下一个总和。这还需要创建一个EnumerateSumsDown()执行相同操作但按降序检索总和的 ，并使用它代替reverse(append(0, EnumerateSums(t.right)))。这样做可以将算法的空间复杂度降低到 O(n)，其中 n 是树中的节点数，因为每个迭代器对象都需要恒定的空间（指向左右子迭代器对象的指针，加上记录迭代器对象的位置）最后的总和）并且每个树节点最多可以有一个。