从给定的后序遍历构造BST [英] Construction of BST from given Postorder Traversal

问题描述

我有一个BST树大小的后置数组n我怎么显示只有一个BST可以用它构造.我知道如果从右到左添加节点，可以重建树，但是如何显示只有一棵右树呢?

I have postorder array of a BST tree size n how do i show there is only one BST that can be constructed form it. I know I can rebuild the tree if I add nodes from right to left but how do I show there is only one right tree?

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

I have tried saying there are two possible trees and tried showing it is not possible but got stuck

推荐答案

仅因为它是BST，才有可能.回想一下，使二叉树成为有效的二叉搜索树:

It is possible only because it is a BST. Recall that for a Binary tree to be a valid Binary Search Tree:

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

-Left subtrees' values must be less than root's value
-Right subtrees' values must be greater than root's value
-Left and right subtrees must be valid binary search trees.

因为我们知道确实是这种情况，所以我们可以给定后顺序的元素列表来重构树.数组中的最后一个元素(在pos n处)是根.找到比根更大的最右元素，这是根的第一个右子树.找到最靠近数组末尾的元素，该元素小于根，这是左边的元素.递归地应用它来获取树.

Because we know this must be the case, we can reconstruct the tree given a list of elements in post-order. The last element in the array (at pos n), is the root. Find the right-most element bigger than the root, and that's the root's first right-subtree. Find the element closest to the end of the array that is smaller than the root, and that's the left element. Recursively apply this to get the tree.

示例:

[8,10,9,12,11]

      11 <----root

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

9 is the right-most number smaller than 11, so it's the left sub-tree

  11
 /
/  

9

并且12是大于11的最右边的元素，所以

and 12 is the right-most element bigger than 11, so

    11
   /  \
  /    \
 9      12

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

Now, our root is 9, and the right-most number smaller than 9 is 8, so tree becomes

       11
      /  \
     /    \
    9      12
   / \ 
  8

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

And the next number bigger than 9 is 10, so the final tree is

       11
      /  \
     /    \
    9      12
   / \ 
  8   10

尝试并说服自己，还有其他可能的有效二进制搜索树包含这些点，但不是在后遍历时会产生相同的输出.

Try and convince yourself that there are other possible valid binary search trees with these points, but not ones that produce identical output on a post-order traversal.

这篇关于从给定的后序遍历构造BST的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！