algorithm - BST 到链表并返回同一个 BST

Question

因为我找不到有用的东西所以我在这里问我的问题:

我们如何在不使用任何额外空间的情况下将 BST 转换为中序链接列表，然后再转换回“相同”的 BST。

到目前为止我已经尝试过的(虽然仍在做):我尝试了 Morris Traversal 来链接到下一个有序的继任者，但它无法连接所有节点，仅适用于左子树和右子树，不适用于树的实际根。请建议我如何将 Tree 转换为 Linked List 并返回到 Same tree ...

Answer 1

要将树存储在列表中 - 您至少需要两个列表:一个用于前序遍历，另一个用于中序遍历。

幸运的是 - 由于树是 BST，中序遍历只是排序列表。

因此，你可以存储前序遍历(你可以尝试原地做)并且通过在重构中对元素进行排序，你可以获得中序遍历。

This post讨论了如何根据树的中序遍历和预序遍历重建树。