BST二叉搜索树的后序遍历 （Java实现）_java bst 后序遍历

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。

假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        int len_sq = sequence.length;
        if( sequence == null || len_sq == 0) { return false; }  // 注意，此处容易漏掉一个判断条件， java中的数组可以为null 或者[]， 所以两种情况都考虑一下
 
        return isSquenceOfBST(sequence, 0, len_sq-1); //引入一个辅助函数，用于判断这个 BST是否合法。 （此处是从后序的角度考虑问题的）
    }
   
    public boolean isSquenceOfBST(int [] sequence, int start, int end) {
        if(start >= end) return true;
        
        int rootvalue = sequence[end]; // 先确认一下这个数组的根节点的值
        
        int mid;
        for(mid=start; mid <end; mid++) {  // 找到左右子树的中间点，当右子树第一个节点大于根节点的时候，中断，记下右子树第一个节点的下标；
            if(sequence[mid] > rootvalue) {
                break;
            }
        }
        
        for(int j = mid; j<end; j++){  // 上一个for循环已经对左子树进行了遍历， 现在对右子树中的节点进行遍历； 若有节点值小于根节点的值，直接返回false； 为什么此处j < end， 而不是j<=end? 因为下标为end的值就是根节点，直接去除即可；
            if(sequence[j] < rootvalue) {
                return false;
            }
 
        }
        
//继续对左右子树进行递归判断
        return isSquenceOfBST(sequence, start, mid-1) && isSquenceOfBST(sequence, mid, end-1);
    }
    
}

难点：

1，边界条件的考虑； 什么时候用< ，什么时候用<=； 

2， 这道题其实就是判断 BST二叉树的合法性。 当判断的时候，一定要利用 BST二叉搜索树的本身特性：  左子树的所有节点都比根节点的值小； 右子树的所有节点都比根节点的值大；