如何检查给定的数组是否表示二进制搜索树的后序遍历

Question

有一个给定的数组，我们需要知道它是否代表BST的后序遍历

Answer 1

使用以下代码可以估计给定数组是否可以表示BST。

程序：

10
/  
7   12
/     
6   9    31
/
14

设数组为arr={6,9,7,14,31,12,10}

现在，我们开始从末尾遍历数组，直到到达元素小于endindex的索引(arr[endindex]=10)。我们将该索引存储在temp中。(这里temp＝2，即arr[temp]=7为7<10)我们再次从temp遍历到startindex。如果我们找到一个大于10的数字(最后一个索引的元素)，我们会返回false。如果不是，遍历到startindex。现在我们将数组分成两半{6,9,7}和{14,31,12,10}。并对两者遵循相同的程序。

逻辑：

post-order表示｛｛LEFT元素｝、｛RIGHT元素｝和｛ROOT｝｝。因此数组的顺序应该是{(元素小于父元素)，(元素大于父元素)、(父元素)}

这是我们在遍历数组时要确保的。

代码如下：

public class ckeckIfPostOrderAbinaryTree {
public static void main(String[] args) {
int[] arr={6,9,7,14,31,12,10};
System.out.println(solve(arr,0,arr.length-1));
}
public static boolean solve(int[] arr,int strt,int end){
if(strt>=end){
return true;
}
int x=arr[end],index=end-1;
while(index>=strt && arr[index]>x){
index--;
}
int temp=index;
while(index>=strt){
if(arr[index]>x){
return false;
}
index--;
}
if(temp==strt){
return solve(arr,strt,end-1);
}
else{
return (solve(arr,strt,temp) && solve(arr,temp+1,end-1));
}
}
}

Answer 2

Postorder遍历由｛LEFT Subtree｝｛Right Subtree}｛ROOT｝完成。因此，这里的想法是从右端开始遍历数组。数组中的最后一个元素是根，从右到左，当你遇到较小的元素时，它标记了从左子树开始的边界，BST不会有这个索引中的较大元素，这适用于每个子树。C++中的算法是这样的-

bool isBST(int arr[], int n){
//Set root to the max integer value.
int root = INT_MAX;
//Stack used to keep track of current subtree
std::stack<int>s;
//Start at the end of the array because Postorder traversal is
// <L><R><D>
for (int i = n-1; i>=0; i--) {
//False if any larger number in the left subtree
if (arr[i]> root) {
return false;
}
//Reset the root for boundary of every subtree,
//when current item is smaller than top,
//that means we are starting with left subtree of this root
while (!s.empty() &&  arr[i] < s.top()) {
root = s.top();
s.pop();
}
//Keep pushing the elements otherwise
s.push(arr[i]);
}
return true;

}

Answer 3

快速健全性检查：如果数组中的最后一项不是根节点，那么它就不是订单后遍历的结果。类似地，如果进行了预购遍历，数组中的第一个项就是根。