algorithm - 在 BST 中打印后继者和前任者

Question

我的问题如下:

我有一个带键的二叉搜索树:a1<a2<...<an ，问题是在 O(n) 时间内使用递归算法在没有任何全局变量的情况下打印树中的所有 (a_i, a_i+1) 对(其中 i={1,2,3,...})使用 O(1) 额外空间。一个例子:让键为:1,2, ..., 5将打印的对:(1,2) (2,3) (3, 4) (4, 5)

所以你不能在树中进行中序遍历并找到每个节点的后继/前任。因为这将花费 O(nh) 时间，如果树是平衡的，则整棵树的时间为 O(nlgn)。

Answer 1

尽管您认为找到有序的后继者或前任者可能需要 O(h) 时间是对的，但事实证明，如果您从 BST 中的最小值开始并反复寻找其后继者，则完成的工作总量无论树的形状如何，最终都会出现 O(n)。

对此的直觉是考虑在迭代执行后继查找时遍历树中每条边的次数。具体来说，您将恰好访问树中的每条边两次:一次是当您进入子树时，一次是当您离开子树并访问该子树中的每个节点时。由于 n 节点树有 O(n) 条边，因此这需要时间 O(n) 才能完成。

如果您对此持怀疑态度，请尝试编写一个简单的程序来验证它。我记得我第一次听到这个结果时并不相信，直到我写了一个程序来证实它。 :-)

在伪代码中，逻辑如下所示:

1. 通过从根开始并重复跟随左子指针直到不存在这样的指针，找到树中的最低值。
2. 直到访问完所有节点，记住当前节点并找到它的后继节点，如下所示:
   1. 如果当前节点有右 child :
      1. 向右走。
      2. 向左走，直到没有剩下的 child 为止。
      3. 输出你开始的节点，然后是这个节点。2:否则:
      4. 向上走到父节点，直到您发现开始的节点是其父节点的左子节点。
      5. 如果您找到了根并且从未发现您是从左 child 向上遍历的，那么您就完成了。
      6. 否则，输出你记得的节点，然后是当前节点。

希望这对您有所帮助!