二叉搜索树（篇1）判断数组是不是二叉搜索树后序遍历的结果

本文主要是介绍二叉搜索树（篇1）判断数组是不是二叉搜索树后序遍历的结果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉搜索树（Binary Search Tree），
它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

这里写图片描述

上图中的二叉搜索树的后序遍历在数组中是：2 9 5 15 16 17 19 18 12

思路：
数组中的最后一个节点是树的根节点，根节点右边的值都比根节点大，左边的值都比根节点小，因此数组中从后往前找所有比根节点大的都放在右子树，然后看后面的是不是都比根节点小，如果还有比根节点大的返回FALSE，如果没有则递归检查右子树和左子树。

代码

public boolean VerifySquenceOfBST(int [] sequence) {return VerifySquenceOfBST(sequence,0,sequence.length-1);}public boolean VerifySquenceOfBST(int [] sequence,int start,int end) {if(start>=end){return true;//如果数组中只有一个节点返回TRUE}int right=start;int point=sequence[end];int i=end-1;    for(;i>=0;i--){if(sequence[i]<point){right=i;break;//标记右子树上节点的最左边位置}}for(;i>=0;i--){if(sequence[i]>=point){return false;//如果左子树上有比根节点大的值返回false}}return VerifySquenceOfBST(sequence,right+1,end-1)&&VerifySquenceOfBST(sequence,start,right);}