algorithm - 二叉搜索树 (BST) 中的数字与某个值相加

Question

给定一个 BST，是否有可能在 O(n) 时间和很少的额外内存中找到两个加起来等于给定值的数字。通过一点额外的内存，这意味着您不能将整个 BST 复制到一个数组中。

Answer 1

如果您同时拥有子指针和父指针，这可以在 O(n) 时间和 O(1) 额外内存中完成。你保留两个指针，x 和 y，x 从最小元素开始，y 从最大元素开始。如果这两个元素的总和太低，则将 x 移至其后继，如果太高，则将 y 移至其前任。一旦 x 指向比 y 更大的元素，您就可以报告失败。树中的每条边最多遍历两次，总共 O(n) 次边遍历，您唯一的内存使用是两个指针。如果没有父指针，您需要记住根的祖先序列，它至少是 Omega(log n)，如果树不平衡则可能更高。

要查找继任者，可以使用以下伪代码(前任的类似代码):

succ(x) {
  if (x.right != null) {
    ret = x.right;
    while (ret.left != null) ret = ret.left;
    return ret;
  } else {
    retc = x;
    while (retc.parent != null && retc.parent < x) retc = retc.parent;
    if (retc.parent != null && retc.parent > x) return retc.parent;
    else return null;
  }
}