题解 | #二叉搜索树的后序遍历序列#

题目：二叉搜索树的后序遍历序列
描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）
思路1：一个二叉搜索树的后序遍历序列，最后一个元素必定是根节点，序列中从第一个到最后一个比最后一个节点值小的就是左孩子的元素，之后的元素到序列最后一个元素之前，就是右孩子节点，若序列无序，则说明这个序列不是不是某二叉搜索树的后序遍历的结果。本题中，输入序列[4,8,6,12,16,14,10]，经过分析，[4,8,6]为二叉树左孩子，[12,16,14]为右孩子，可得如图二叉树：

Java代码如下：

import java.util.Arrays;
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null||sequence.length<=0){
            return false;
        }
        int len=sequence.length;
        int root=sequence[len-1];
        int i=0;
        for(;i<len-1;i++){
            if(root<=sequence[i])
                break;
        }
        int j=i;
            for(;j<len-1;j++){
                if(root>sequence[j]){
                    return false;
                }
            }
            boolean leftFlag=true;
            if (i>0) {
                leftFlag=VerifySquenceOfBST(Arrays.copyOfRange(sequence,0,i));
            }
            boolean rightFlag=true;
            if (i<len-1) {
                rightFlag=VerifySquenceOfBST(Arrays.copyOfRange(sequence,i,sequence.length-1));
            }
            return leftFlag&&rightFlag;
        }

}

时间复杂度：利用for循环确定左右子树的元素，时间复杂度为0(N)。
思路2：借助“栈”的思想，二叉树的中序序列和后序序列经过栈的压入弹出可以进行转化，
本题中输入[4,8,6,12,16,14,10]，把中序序列当做栈的压入序列，那么后序序列应该是该栈的一个弹出序列。

Java代码如下所示：

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

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        int [] arr = sequence.clone();
        //中序遍历结果即排序后的结果。
        Arrays.sort(arr);

        return IsPopOrder(arr , sequence);
    }


    private boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length == 0|| popA.length == 0){
            return false;
        }

        Stack<Integer> tmp = new Stack<>();
        int len = pushA.length-1;
        int i = 0 ;
        int num = 0;

        while(i<=len){
            tmp.push(pushA[i]);
            while(!tmp.isEmpty() && tmp.peek() == popA[num]){
                num++;
                tmp.pop();
            }
            i++;
        }
        return tmp.isEmpty();
    }
}

时间复杂度：用栈的思想对树进行遍历，时间复杂度为0(N)。