算法—判断二叉搜索树的后序遍历序列

题目

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

方法1

利用后序遍历序列的性质： 1.最后一个元素是根节点root； 2.除去root后的序列，前面是根节点的左子树left，后面是根节点的右子树right； 3.左子树序列一定都要比root小，右子树序列一定都要比root大. 4.对左子树和右子树的序列同样满足以上三点

代码

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0){  //空树
            return false;
        }
        if(sequence.length == 1){
            return true;
        }
        return VerifyHelper(sequence, 0, sequence.length-1);  //调用辅助函数
    }
    public boolean VerifyHelper(int [] sequence, int start, int end){
        if(start >= end){
            return true;  //全部节点都验证完了
        }
        int root = sequence[end]; //找到根节点
        int i = start;
        while(i<end && sequence[i]<root){
            i++;  //找到左右子树序列的临界点
        }
        for(int j=i; j<end; j++){
            if(sequence[j] < root){ //若右子树序列里存在小于root的节点，返回false
                return false;
            }
        }
        //分别判断左子树，右子树序列
        Boolean result1 = VerifyHelper(sequence, start, i-1);
        Boolean result2 = VerifyHelper(sequence, i, end-1);
        return result1 && result2;
    }
}

方法二

转换成算法：给出一个序列作为入栈顺序，判断另一个序列能否为它的出栈顺序。 1.二叉树的中序遍历序列和后序遍历序列，恰好是一个栈的入栈顺序和出栈顺序； 2.二叉搜索树的中序遍历序列是一个有序序列； 3.可将后序序列排序，得到中序序列，判断将中序序列入栈，后序序列能否是它的出栈顺序

代码

import java.util.Arrays;
import java.util.Stack;

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        int inOrder[] = sequence.clone();
        Arrays.sort(inOrder); //得到中序序列
        return isPopOrder(inOrder, sequence);
        }
    public boolean isPopOrder(int pushOrder[], int popOrder[]){
            if(pushOrder.length==0 || popOrder.length==0){
                return false;
            }
            Stack<Integer> stack = new Stack<>();
            int p = 0;
            for(int i=0; i<pushOrder.length; i++){
                stack.push(pushOrder[i]);//将入栈序列一一入栈
                while(!stack.isEmpty() && stack.peek()==popOrder[p]){//遇到和出栈序列相同的元素，就出栈
                    stack.pop();
                    p++;
                }
            }
            return stack.isEmpty();
    }
    }