描述

思路1：分治

1. 后序遍历最后一个元素一定是是根节点，先遍历完左子树，再遍历右子树。
2. 找到第一个比根节点大的数，即左子树和右子树的分界点。
3. 将序列分为三段[4,8,6,12,16,14,10]，根节点为10，左子树为[4,8,6]，右子树为[12,16,14]
4. 左子树都小于根节点，右子树都大于根节点。否则不是二叉搜索树
5. 分治：对左右子树分别递归判断

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0) {
            return false;
        }
        return recur(sequence, 0, sequence.length - 1);
    }
    boolean recur(int[] sequence, int left, int right) {
        if(left >= right) {
            return true;
        }
        //后序遍历最后一个元素是根节点
        int root = sequence[right];
        int i = left;
        //找到第一个比根节点大的数，即右子树后序遍历的第一个节点
        while(i < right) {
            if(sequence[i] > root) {
                break;
            }
            i++;
        }
        //i左边都小于根节点
        int j = left;
        while(j < i) {
            if(sequence[j] > root) {
                return false;
            }
            j++;
        }
        //i右边都大于根节点
        while(j < right) {
            if(sequence[j] < root) {
                return false;
            }
            j++;
        }
        //对左右子树分别递归，判断是否符合条件
        return recur(sequence, left, i - 1) && recur(sequence, i, right - 1);
    }
}

优化：第一个循环和第二个循环可以合并

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0) {
            return false;
        }
        return recur(sequence, 0, sequence.length - 1);
    }
    boolean recur(int[] sequence, int left, int right) {
        if(left >= right) {
            return true;
        }
        //后序遍历最后一个元素是根节点
        int root = sequence[right];
        int i = left;
        //找到第一个比根节点大的数
        while(i < right && sequence[i] < root) {
            i++;
        }
        int mid = i;
        //i右边都大于根节点
        while(i < right) {
            if(sequence[i] < root) {
                return false;
            }
            i++;
        }
        //对左右子树分别递归，判断是否符合条件
        return recur(sequence, left, mid - 1) && recur(sequence, mid, right - 1);
    }
}

思路2：栈+逆序遍历

后序遍历序列的逆序即为根节点->右节点->左节点。例如[4,8,6,12,16,14,10]

1. 根节点为10，入栈
2. 14>10，则为10的右节点，入栈
3. 16>14，则为14的右节点，入栈，栈中元素为[10,14,16]
4. 12不断和栈顶元素比较，直到12大于栈顶元素[10]，假设栈顶之上保存了上一个出栈的元素为root=14，则12是root的左节点，入栈，此时栈中元素为[10,12]

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0) {
            return false;
        }
        Stack<Integer> stack = new Stack<>();
        int i = sequence.length - 1;
        int root = Integer.MAX_VALUE;
        while(i >= 0) {
            if(sequence[i] > root) {
                return false;
            } else {
                while(!stack.isEmpty() && stack.peek() > sequence[i]) {
                    root = stack.pop();
                }
                stack.push(sequence[i]);
            }
            i--;
        }
        return true;
    }
}

思路3：栈

将序列从小到大排序，即得到二叉树的中序遍历结果，判断后序遍历序列是否是合法出栈序列