剑指Offer-二叉搜索树的后序遍历序列

Dear 丶 2022-02-26 10:58 182阅读 0赞

## 题目描述 ##

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

解题思路—**递归**：只要跟树有关的题目，几乎都会用到**递归**！如何找到递归切入点是最重要的。首先我们要理解什么是**二叉搜索树**，二叉搜索树的所有根结点一定大于左子结点，一定小于右子节点。题目输入的是二叉搜索树的后序遍历数组，根据后序遍历的顺序：**左子树-右子树-根**，可以得知输入数组的前半部分为左子树，后半部分为右子树，最后一个为根节点。于是，如何判断数组是否为二叉搜索树，只要**满足数组的左半部分都小于根，右半部分都大于根**即可。  
解题思路—**非递归**：在网上还看到了一个很巧妙的非递归写法，其实核心思想跟递归是一致的，递归是从中间将数组分割开分别进行判断，非递归就是从数组尾部向前判断。非递归代码写的也很简洁，可读性也很高。就是需要注意一下判断条件，防止数组越界。

> **注：一些简单的判断就不要用递归了！不要轻易使用嵌套递归！非常容易递归到死。**

## Java解题—递归 ##

public class Solution {
        public boolean VerifySquenceOfBST(int [] sequence) {
            if(sequence.length==0)
                return false;
            if(sequence.length==1)
                return true;
            return Judge(sequence, 0, sequence.length-1);
        }
        public boolean Judge(int[] seq, int start, int end){
            // seq判断完毕
            if(start>=end)
                return true;
            int i=0;
            while(seq[i]<seq[end])
                i++;
    
            for(int j=i;j<end;j++){
                if(seq[j]<seq[end])
                    return false;
            }
            return Judge(seq, start, i-1) && Judge(seq, i, end-1);
        }
    }

## Java解题—非递归 ##

在这里插入代码片public class Solution {
        public boolean VerifySquenceOfBST(int [] sequence) {
            int length = sequence.length;
            if(length==0)
                return false;
    
            int i=0;
            while(--length>0){
                while(sequence[i++]<sequence[length]);
                while(i<=length && sequence[i++]>sequence[length]);
                if(i<length)
                    return false;
                i=0;
            }
            return true;
        }
    }