二叉搜索树中倒排后序遍历与插入顺序之间的联系

Question

• 我有一个二叉搜索树。
• 我进行了后序遍历。
• 我颠倒了从后序遍历中获得的数据序列的顺序（例如通过 将数据插入堆栈，然后再次弹出。）
• 现在，我开始将新的数据序列插入到新的空 BST 中。
• 结果是一个新的 BST，与原始的相同。

我的问题是为什么？在 BST 中插入数据的顺序和倒序后遍历之间是否存在根本联系？我知道BTS的结构是由你插入数据的顺序决定的，但是我找不到这两者之间的联系。

这实际上是我在线CS课程中的一个练习。我知道新树必须与原始树相同，因为这是本练习的重点。我找不到的是解释，我看不出任何联系。

Answer 1

更新：正如一位朋友指出的，它必须是根。通过反转后序遍历，遇到的第一个节点是原始 BTS 的每个子树的根。因此，通过插入相同的根，会产生原始子树的副本，并递归整个 BST