每日算法之二叉搜索树的后序遍历序列
JZ33 二叉搜索树的后序遍历序列描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。
提示：
1.二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。
2.该题我们约定空树不是二叉搜索树
3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历思路
BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，
那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，
且这两段（子树）都是合法的后序序列。完美的递归定义代码
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; int i = start; //左子树遍历 while (i
页:
[1]