二叉搜索树的后序遍历序列

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

思路1，得到中序遍历结果，根据后续及中序结果，重建树结构，左树上的点要比根小，右树上的点要比根大。

import java.util.*;
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null||sequence.length==0)
            return false;
        int[] mid = new int[sequence.length];
        for (int i = 0; i < sequence.length; i++)
            mid[i] = sequence[i];
        Arrays.sort(mid);
        return helper(sequence,0,sequence.length-1,mid,0,sequence.length-1);
    }

    private boolean helper(int[] last, int lastL, int lastR, int[] mid, int midL, int midR) {
        if (lastL>=lastR)
            return true;
        int root = last[lastR];
        int i = midL;
        for (;i<=midR;i++)
            if (root==mid[i])
                break;
        return judgeL(last,lastL,i-midL+lastL-1,root)&&
        judgeR(last,i-midL+lastL,lastR-1,root)&&
        helper(last,lastL,i-midL+lastL-1,mid,midL,i-1)&&
        helper(last,i-midL+lastL,lastR-1,mid,i+1,midR);

    }

    private boolean judgeR(int[] last, int lastL, int lastR, int root) {
        for (int i = lastL;i<=lastR;i++)
            if (last[i]<root)
                return false;
        return true;
    }

    private boolean judgeL(int[] last, int lastL, int lastR, int root) {
        for (int i=lastL;i<=lastR;i++)
            if (last[i]>root)
                return false;
        return true;
    }
}

思路2：直接根据后续遍历结果，从后向前找到第一个比根小的节点，那么该节点前面的节点都应该比根小，否则不符合二叉搜索树的特点。

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence==null||sequence.length==0)
            return false;
        return helper(sequence,0,sequence.length-1);
    }

    private boolean helper(int[] sequence, int l, int r) {
        if (l>=r)
            return true;
        int i = r-1;
        while (i>=l&&sequence[i]>sequence[r])
            i--;
        for (int j=l;j<i;j++)
            if (sequence[j]>sequence[r])
                return false;
        return helper(sequence,l,i)&&helper(sequence,i+1,r-1);
    }
}