根据给定的后序遍历构建 BST

Question

我有一个 BST 树大小的后序数组，我如何表明只有一个可以从它构造的 BST。我知道如果我从右到左添加节点，我可以重建树，但如何显示只有一棵右树？

我试图说有两棵可能的树，并试图证明这是不可能的，但被卡住了

Answer 1

这是可能的，因为它是 BST。回想一下，要使二叉树成为有效的二叉搜索树：

-左子树的值必须小于根的值
-右子树的值必须大于根的值
-左子树和右子树必须是有效的二叉搜索树。

因为我们知道情况一定如此，所以我们可以在给定后序元素列表的情况下重建树。数组中的最后一个元素（位于 pos n）是根。找到比根大的最右边的元素，这就是根的第一个右子树。找到最接近数组末尾且小于根的元素，这就是左边的元素。递归地应用它来获取树。

例子：

[8,10,9,12,11]

      11 <----root

9是比11更小的最右边的数字，所以它是左子树

  11
 /
/  

9

12 是比 11 大的最右边的元素，所以

    11
   /  \
  /    \
 9      12

现在，我们的根是 9，最右边小于 9 的数字是 8，所以树变成

       11
      /  \
     /    \
    9      12
   / \ 
  8

下一个大于 9 的数字是 10，所以最终的树是

       11
      /  \
     /    \
    9      12
   / \ 
  8   10

尝试并说服自己，存在其他可能具有这些点的有效二叉搜索树，但不会在后序遍历中产生相同的输出。