本文主要是介绍剑指Offer之二十四-二叉搜索树的后序遍历序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
- 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
- 如果是则返回ture,否则返回false。
- 假设输入的数组的任意两个数字都互不相同。
解析
- 找到根结点
- 从头遍历序列，第一个比根结点大的元素为右子树的起点
- 判断右子树是否都比根结点大，若不是返回false，若是，进行下一步
- 分别把左子树和右子树都以上面规则进行判断，若左右子树都能返回true，则整个序列为二叉搜索树的后序遍历序列，返回true
代码实现
public boolean verifySquenceOfBST(int [] sequence) {if(sequence == null || sequence.length == 0){return false;}int len = sequence.length;int root = sequence[len - 1];int i = 0;for(; i < len - 1; i++){if(sequence[i] > root){break;}}int j = i;for(;j < len - 1; j++){if(sequence[j] < root){return false;}}boolean left = true;boolean right = true;if(i > 0){left = verifySquenceOfBST(Arrays.copyOfRange(sequence, 0, i));}if(i < len - 1){right = verifySquenceOfBST(Arrays.copyOfRange(sequence,i,len - 1));}return left && right;
}<p></p>
这篇关于剑指Offer之二十四-二叉搜索树的后序遍历序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
