c - 在 BST 中找到添加到 k 的节点对

Question

这是一道面试题。给定一个完整的 BST，找到所有节点对，其值与给定的和 k 相加。不应使用额外的空间，时间应为 O(n)，并且不允许进行最佳修改。面试官给了 15 分钟的时间来提出算法和代码。我能够看到其他解决方案，但无法找到满足给定约束的任何解决方案

Answer 1

没有多余的空间？要遍历树，您需要一些堆栈……除非节点有父指针……所以让我们假设您可以使用一些堆栈。显然，如果您按升序排列这些值，您可以找到总和为“k”的所有对。所以:将树遍历到最小，构造一个显式堆栈——即，不递归。复制堆栈。现在您可以从那里按升序进行两次步行。

---

进一步思考，假设我们运行一个中序遍历，在每个阶段我们都有一个我们称之为 l 的值。 , 以及当前值的逆序遍历 r .在任何给定点我们有s == l + r ，并且我们已经考虑了 l 左侧的所有内容在 r 的右边.如果s < k ，我们前进到下一个(更大的)l , 如果 s > k我们退回到下一个(较小的)r , 如果 s == k我们有答案。 (我想我们可以假设树中的所有值都是唯一的，但如果不是，我们可能不得不考虑给定 l 和 r 的多个实例，它们给出 k。

实现这个的关键是前向扫描函数:

  int forw(node* root, int l, int r, int k)

首先搜索节点 l ，然后继续直到 l + r >= k .

还有一个类似的函数以另一种方式移动。

这些可以通过为每个显式堆栈非常有效地实现，这避免了必须首先向下递归(重新)找到 l 的树位置。或 r ...我指出，与递归函数方法相比，显式堆栈不使用额外内存——实际上，可能使用较少堆栈:-)

此外，重新查找树的位置可以说比 O(n) 更糟糕——添加 O(log(n)) 的数量，每次重新开始向前和向后扫描时一个。