您将获得n个元素1,2，…，n]上的二叉搜索树的后序遍历P，>

Question

您将获得n个元素1,2，…，n上二叉搜索树的后序遍历P。您必须确定以P作为其后序遍历的唯一二进制搜索树。最有效的算法执行此操作的时间复杂度是多少？

A。 Θ（登录）

B。 Θ（n）

C。 Θ（nlogn）

D。以上都不是，因为无法唯一地确定树]

我的理解：

根据给定的后序遍历，我们可以计算lg（n）时间中的有序遍历。由于我们已经计算了有序遍历，因此我们可以将元素分为两部分，因为根元素将成为我们的枢轴元素。

我不知道我是否正确理解它，您能帮助我形象化这个概念吗？

您将获得n个元素1,2，…，n上二叉搜索树的后序遍历P。您必须确定以P作为其后序遍历的唯一二进制搜索树。什么是...

Answer 1

必须为Θ(nlogn)。您将必须至少遍历n个节点，然后构建二叉树。