剑指Offer33:二叉搜索树的后序遍历序列

骑猪看日落 2022-02-15 14:38 144阅读 0赞

题目：输入一个数组，判断该数组是否是某二叉搜索树的后序遍历结果，如果是返回true，不是返回false。假设输入的数组的任意两个数字都不相同，例如，输入数组\{5,7,6,9,11,10,8\},返回true,因为满足书上的树，如果输入的是\{7,4,6,5\},因为不满足这个树，所以返回fasle.

思路：后序遍历，最后一个节点都是根节点，那么从开始一定是左子树的节点部分，后面紧接着的是右子树的部分节点，最后才是根节点，如果只单独看左子树节点部分，又是一个满足先遍历左子树和右子树再是根节点的思路，那么问题的规模减小，处理方法一样这就能用到递归来处理了。

但是知道用递归方法来求解，但是思路的起点是什么？？ 因为，递归是处理方法一样，那么我们就应该是从处理单个情况开始考虑，然后再本方法中进行调用本方法（进行递归就好了）.

写递归方法，一定要有递归的终点，而本题的终点就是，当root==null||length-1<=0return false.

而一般递归到只有一个节点就不递归下去了。这个部分应该写在递归体这.每一个变量的设置，都应该想着只处理当前情况就好了，当前情况需要，那么就有存在的理由，同时如果如果当前的递归方法需要返回一个值，那么必先定义一个变量。

然后根据条件进行递归就好了。

先定义int i 遍历完子左子节点，定义int j = i, 遍历右子节点，最后再根据条件，来判断i>0左子树递归，j<length-1右子树递归，同时递归的数据规模进行减小。当递归只有一个数怎么处理呢？就都不会进行递归，而是返回。

代码:

/**
         * 验证一个数组是否是二叉搜索树
         * @param sq
         * @param length
         * @return
         */
        boolean VerifSquenceOfBST(int[] sq,int length){
    
            if(sq==null || length<=0){
    
                return false;
            }
    
            //拿当前的节点，递归即也是length-1的点
            int root = sq[length-1];
    
            //拿左边的点
            int i = 0;
    
            for(;i<length-1;i++){
                //即找到第一个大于root的点为i跳出去
                if(sq[i]>root){
                    break;
                }
            }
    
            //拿右边的点
            int j = i;
            for(;j<length-1;j++){
                //当右边的一些数字有比root小的代表不符合,return fasle
                if(sq[j]<root){
                    return false;
                }
            }
    
            boolean left = true;
    
            if(i>0){
                left = VerifSquenceOfBST(sq,i);
            }
    
            boolean right = true;
    
            if(i<length-1){
    
                right = VerifSquenceOfBST(sq+i,length-i-1);
    
            }
    
            return(left&&right);
    
        }
    
        public static void main(String[] args) {
    
            int[] nums = {5,7,6,9,11,10,8};
    
            System.out.println(new SOfBST().VerifSquenceOfBST(nums,nums.length));
    
        }