判断给定的整数数组是不是某二叉搜索树的后序遍历的结果 -ag凯发k8国际

又：二叉查找树（binary search tree），二叉排序树；

它或者是一棵空树，或者是具有下列性质的二叉树：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。

数大于根肯定往根的右子树走，小于往左子树走

 

左子->右子->根

给出的整数数组：a[n]

method(a[n])

为空，返回false；只有一个元素，返回true;

root=a[n-1];

从0~n-2找出第一个a[i]>root（没找到，则都为左子树）

若i0，有左子树

0~i-1是左子树，method(a[i-1])

如果a[i]~a[n-2]都大于root，则i~n-2是右子树，method(a[n-1-1])，否则返回false(不符合之前的“大于root都在右子树”的定义)

return 3.2&3.3

public class solution { public static boolean verifysquenceofbst(int [] sequence) {int index;boolean rflag=false;boolean lflag=false;int n=sequence.length;if(n==0)return false;if(n==1)return true;int root=sequence[n-1];index=findindex(sequence,root);for(int i=index 1;i0) {int lenl=index;int[] arrl=new int[lenl];for(int i=0;ival)return i;}return n-2;} }

 

总结

以上是ag凯发k8国际为你收集整理的判断给定的整数数组是不是某二叉搜索树的后序遍历的结果的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得ag凯发k8国际网站内容还不错，欢迎将ag凯发k8国际推荐给好友。