假设我们有中序遍历order和后序遍历。例如: 按顺序:30 40 45 50 65 70 80 后序:30 45 40 65 80 70 50
我知道如何从给定的中序遍历和后序遍历构造二叉搜索树，但我的问题是如果给出后序遍历，B.S.T 构造的平均和最坏情况时间复杂度是多少？
最佳答案
在这两种情况下，对于朴素的 BST 构造算法，时间都是 O(n^2)，因为:
在有序的情况下，算法将添加到右边
在后序的情况下，算法将添加到左侧
所以 T(n) = 1 + 2 + 3 + ... n-1 = O(n^2)
UPDATE_3:但在后序情况下，我们可以简单地将每个下一个元素添加为根(前一棵树成为左儿子)，因此复杂度为 O(n)
更新:当然，数字排列的平均时间是 O(n logn)，但在那些情况下，这次时间是 O(n^2)(n 是数字的数量)
UPDATE_2:有关更多详细信息，请查看底部的评论。
关于algorithm - 查找构建二叉搜索树的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31947560/