查找 BST 中的所有连续数字对

Question

我需要编写一个代码来查找 BST 中的所有连续数字对。

例如：让我们以密钥 9 的 BST T 为例，T.left.key = 8，T.right.key = 19。只有一对 - (8, 9).

我想到的天真的解决方案是在 BST 上进行任何遍历（pre，in，post）并为每个节点找到其后继者和前任者，如果其中一个或两个是连续到节点 - 我们将打印它们。但问题是它会是 O(n^2)，因为我们有 n 个节点，对于每个节点，我们使用的函数需要 O( h),即最坏情况下h~n.

第二种方案是将所有元素复制到一个数组中，并在数组中找到连续的数字。这里我们使用 O(n) 附加 space，但是运行时间更好 - O(n).

你能帮我找到一个有效的算法吗？我正在尝试考虑不使用额外 space 的算法，其运行时间优于 O(n^2)

*所需的输出是那些对的数量（不需要打印对）。

*BST中任意2个连续整数为一对

*BST 仅包含整数。

谢谢！

Answer 1

你为什么不直接进行中序遍历并即时计算对数呢？您需要一个全局变量来跟踪最后一个数字，并且需要将其初始化为 not 比第一个数字小一个的值（例如树）。我的意思是：

// Last item
int last;

// Recursive function for in-order traversal
int countPairs (whichever_type treeRoot)
{
  int r = 0; // Return value

  if (treeRoot.leftChild != null)
    r = r + countPairs (treeRoot.leftChild);

  if (treeRoot.value == last + 1)
    r = r + 1;

  last = treeRoot.value;

  if (treeRoot.rightChild != null)
    r = r + countPairs (treeRoot.rightChild);

  return r; // Edit 2016-03-02: This line was missing
}

// Main function
main (whichever_type treeRoot)
{
  int r;

  if (treeRoot == null)
    r = 0;
  else
  {
    last = treeRoot.value; // to make sure this is not one less than the lowest element
    r = countPairs (treeRoot);
  }

  // Done. Now the variable r contains the result
}

查找 BST 中的所有连续数字对

Find all pairs of consecutive numbers in BST

binary-search-tree