JZ23 二叉搜索树的后序遍历序列
描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜索树）
示例
输入：
[4,8,6,12,16,14,10]
返回值：
true
解析
二叉搜索树（ Binary Search Tree ）的特点为左子树的值均小于根节点的值，右子树的值均大于根节点的值，在后序遍历序列中，数组末尾即是根节点的值，因此可以将遍历序列分为三部分
- 数组最后一个，是根节点的值
- 从头开始遍历数组，遇到第一个大于根节点的值时停止
- 该位置左边就是左子树，右边就是右子树
划分出左右子树后，就可以根据二叉搜索树的性质判断它是否合法了，即继续遍历右子树序列，若没有值小于根节点的值（右子树的值都得大于根节点的值），则目前的结构是正确的（指目前根节点、左子树、右子树三部分，此处还未深入到整棵树）。
其中，二叉搜索树中的子树都是二叉搜索树，即对划分出的左子树和右子树进行递归判断，就可知这整棵树是否为二叉搜索树。此处与 JZ17 树的子结构 类似，都要进行递归判断子树，所以可知返回值格式应该是
return Function(left) && Function(right);
代码清单
public class Solution {
// 外部函数入口
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length == 0) return false;
// 目前整个序列都是二叉搜索树
return PostOrder(sequence,0,sequence.length-1);
}
public boolean PostOrder(int [] sequence,int start,int end){
// start = end 时，数组只有一个元素，即没有叶子的根节点
// start > end 时，数组只有一半的元素，即根节点和它的左子树或右子树，另一半为空
if( start >= end ) return true;
int root = sequence[end];
int s = start;
// 从第一个比根节点大的点开始，划分左右子树
while(sequence[s] < root){
s++;
}
// mid 所在的位置区分了左右子树
int mid = s;
// 继续遍历检查右子树，必须得比根节点大
int m = mid;
while(m < end){
if(sequence[m] < root){
return false;
}
m++;
}
// 递归判断该树的左右子树是否合法
return PostOrder(sequence,start,mid-1) && PostOrder(sequence,mid,end-1);
}
}
递归问题都要思考一个关键问题：何时结束递归。在本题中，当传入的数组缩小到只有一个元素时，即 start == end，说明这是没有叶子的根节点，此时可以停止递归，返回 true。
还有另外一种情况，在如下用例中出现
[4,6,7,5]
这种情况是我一开始也没有考虑到的。首先 5 是此树的根节点，4 为左子树，6 7 为右子树；在递归时，传入的子树数组为 [6,7]，此时我们可以知道这颗子树的右子树是为空的！
但程序划分该子树的左右子树时，由于其没有右子树，分割位置 mid 会被置于与 end 相同的位置（若没有左子树则与 start 相同），导致在判断其子树 PostOrder(sequence,mid,end-1) 时（或 PostOrder(sequence,start,mid-1) ），传入的参数中 start 是大于 end 的！
这个信号表明，某节点只有一半的子树，但这一半的子树是合法的（否则在递归到它之前就已经 return false 了），这也符合二叉搜索树的情况，所以在结束递归的条件中，除了 start == end，还要有 start > end，即
// start = end 时，数组只有一个元素，即没有叶子的根节点
// start > end 时，数组只有一半的元素，即根节点和它的左子树或右子树，另一半为空
if( start >= end ) return true;
这就是这种思路解决本题的关键！
总结
树的问题难免涉及树的遍历，在之前确实没说错。这题与之前相似，都要通过递归判断树的结构是否符合条件，温故知新了属于是！