1, 题目描述: 输入一个整数数组, 判断该数组是不是某二叉搜索树的后序遍历的结果. 如果是则输出 Yes, 否则输出 No. 假设输入的数组的任意两个数字都互不相同.
2, 思路: 二叉搜索树就是节点的左子树的值小于该节点的值, 右子树的值大于该节点的值. 所以对于二叉搜索树的后序列, 左 右 根 的遍历顺序, 数组的最后一个值一定是根节点, 而根据二叉搜索树的性质, 左子树的值小于根节点, 右子树的值大于根节点, 通过从前往后遍历数组, 就可以初步找到左右子树的分界, 分界之前一定是左子树, 但是分界之后无法保证所有的值都大于根节点, 因此要校验是否是右子树. 校验完毕后, 就在粗粒度上确定了符合二叉搜索树的条件, 此时再分别将左右子树带入该方法进行迭代, 在细粒度上确定整棵树是否完全符合二叉搜索树的性质.
3, 代码:
- import java.util.*;
- import java.lang.*;
- public class Solution {
- public boolean VerifySquenceOfBST(int [] sequence) {
- // 鲁棒性校验
- if(sequence==null||sequence.length==0){
- return false;
- }
- int length=sequence.length;
- // 数组最后一个数就是根节点的值
- int root=sequence[length-1];
- // 左子节点小于根节点, 右子节点大于根节点, 定位左右子树边界
- // 初步分界, 但右子树不一定符合二叉搜索树定义
- int i=0;
- for(;i<length-1;i++){
- if(sequence[i]>root){
- break;
- }
- }
- // 校验右子树是否符合二叉树定义, 即右子树全大于根节点
- int j=i;
- for(;j<length-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<(length-1)){
- right=VerifySquenceOfBST(Arrays.copyOfRange(sequence,i,length-1));
- }
- return (left&&right);
- }
- }
来源: http://www.bubuko.com/infodetail-3364761.html