每日算法之二叉搜索树的后序遍历序列

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

描述

1. 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。
2. 提示：
3. 1.二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。
4. 2.该题我们约定空树不是二叉搜索树
5. 3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历

复制代码

思路

1. BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，
2. 那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，
3. 且这两段（子树）都是合法的后序序列。完美的递归定义

复制代码

代码

[code]package mid.JZ33二叉搜索树的后序遍历序列;public class Solution {    public boolean VerifySquenceOfBST(int [] sequence) {        if (sequence == null || sequence.length == 0) return false;        return judge(sequence, 0, sequence.length - 1);    }    public boolean judge(int[] sequence, int start, int end) {        //为空        if (start >= end) return true;        //根节点        int root = sequence[end];        int i = start;        //左子树遍历        while (i