我对不同站点上关于从任何一次遍历构建二叉搜索树的文章感到非常困惑(pre，post或 in-order)，或其中任意两个的组合。例如，在 this页面，它表示给定 pre、post 或 level 顺序遍历，以及 in-order 遍历, 可以构建 BST。但是here和 there ，他们向我们展示了如何仅从 pre-order 构造一个 BST。另外，here他们向我们展示了如何从给定的 pre 和 post-order 遍历构建 BST。在其他一些站点中，我找到了一种仅从 post-order 遍历构建 BST 的解决方案。
现在我知道给定inorder 和pre-order 遍历，可以唯一地形成一个BST。至于我提供的第一个链接，虽然他们说我们不能从pre-order和post-order构造BST，但是可以难道我只是对 post-order 数组进行排序以获得它的 inorder 遍历，然后使用它和 pre-order 数组来形成BST？这与第 4 个链接中的解决方案相同还是不同？并且只给定 pre-order，我可以对其进行排序以获得 in-order，然后使用它和 pre-order 来获得BST。同样，这是否必须与链接 2 和 3 中的解决方案不同？
具体来说，什么足以唯一地生成BST？如果不需要唯一性，那么我可以简单地对其进行排序以获得 in-order 遍历，并从中递归地构建 N 个可能的 BST 之一。
最佳答案
要构建 BST，您只需要一次(非有序)遍历。
通常，要构建一棵二叉树，您需要进行两次遍历，例如顺序遍历和预序遍历。但是，对于 BST 的特殊情况 - 中序遍历始终是包含元素的排序数组，因此您始终可以重构它并使用算法从预序和中序遍历重构通用树。
因此，树是 BST 的信息，以及其中的元素(即使是无序的)等同于中序遍历。
奖励:为什么一次遍历对于一般树来说还不够(没有信息它是 BST)？
答案:假设我们有n 个不同的元素。这些 n 元素有 n! 个可能的列表，但是 - 可能的树数要大得多(2 * n! n 个元素的可能树都是腐烂的树, 这样 node.right = null 在每个节点中, 因此树实际上是右边的列表. 有 n! 这样的树, 另外 n! 树在哪里always node.left = null ) 因此，根据鸽巢原理 - 至少有一个列表生成 2 棵树，因此我们无法通过单次遍历重建树。
(QED)
关于algorithm - 构造 BST 需要知道多少次遍历，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12880718/