Sex*_*ast 14 algorithm inorder binary-search-tree postorder preorder
我对不同网站上的一些文章非常困惑,这些文章是关于构建Binary Search Tree任何一个遍历(pre,post或in-order),或者它们中任意两个的组合.例如,在这个页面上,它表示给定pre,post或level顺序遍历,以及in-order遍历,可以构造BST.但是在这里和那里,他们向我们展示了BST从pre-order单独构建一个.此外,他们在这里向我们展示了如何构建BST来自给定pre和post-order遍历.在其他一些网站中,我找到了一个BST仅从post-order遍历构建一个解决方案的解决方案.
现在我知道,给定inorder和pre-order遍历,可以独特地形成一个BST.至于我提供的第一个链接,虽然他们说我们不能构造BSTfrom pre-order和post-order,我不能只是对post-order数组进行排序以获得它的inorder遍历,然后使用它和pre-order数组来形成BST？这与第4个链接中的解决方案相同,还是不同？pre-order只有给出,我可以排序,以获得in-order,然后使用它和pre-order得到BST.同样,这是否必须与链接2和3的解决方案不同？
具体来说,什么足以独特地产生BST？如果不需要in-order唯一性,那么我可以简单地对其进行排序以获得遍历,并以BST递归方式从其中构建N个可能的中的一个.
ami*_*mit 22
要构建BST,您只需要一个(非按顺序)遍历.
通常,要构建二叉树,您需要按顺序进行两次遍历,例如预订.但是,对于BST的特殊情况 - 有序遍历始终是包含元素的排序数组,因此您始终可以重构它并使用算法从预订和按顺序遍历重建通用树.
因此,树是BST的信息及其中的元素(甚至是无序的)等同于有序遍历.
额外奖励:为什么一次遍历对于一般树来说是不够的(没有信息它是BST)？
答:我们假设我们有n不同的元素.然而n!,这些n元素有可能的列表- 树的可能数量要大得多(2*n!n个元素的可能树都是衰变树,因此node.right = null在每个节点中,因此树实际上是右边的列表有n!这样的树,还有另外的n!树总是如此node.left = null)因此,根据鸽子洞的原则 - 至少有一个生成2棵树的列表,因此我们无法从单次遍历中重建树.(QED)