package com.camnter.basicexercises.tree;
/**
* 校验 BST 的后序遍历
*
* 比如,校验 1 2 3 6 5 4 9 10 8 7 是否是一颗 BST 的后序遍历结果
* - 7
* - 4 8
* - 3 5 10
* - 2 6 9
* - 1
*
* 后序遍历的特点:根节点在最后
* BST 后序遍历的特点:比根节点小的数组在前,比根节点小的数组在后
* BST 的后序遍历一定满足这些要求
*
* 比如,1 2 3 6 5 4 9 10 8 7
* [1 2 3 6 5 4] [9 10 8] 7
* 然后,
* 1 2 3 6 5 4 可以划分为 [1 2 3] [6 5] 4
* 9 10 8 可以划分为 [9] [10] 8
* 满足要求
*
* 思路,就是不断划分左右数组
*
* @author CaMnter
*/
public class IsPostOrderArrayOfBST> {
public boolean isPostOrderArrayOfBST(T[] array) {
if (array == null || array.length == 0) {
return false;
}
return isPostOrderArrayOfBST(array, 0, array.length - 1);
}
public boolean isPostOrderArrayOfBST(T[] array, int start, int end) {
if (start == end) {
return true;
}
/**
* less 记录 左数组 最右边那个 value 的 index
* more 记录 右数组 最左边那个 value 的 index
*
* 正常情况的规则上,左右数组相邻
*/
int less = -1;
int more = end;
for (int i = start; i < end; i++) {
if (array[end].compareTo(array[i]) > 0) {
less = i;
} else {
/**
* 非常有趣的是
*
* 在 else 进去一次后
* more 的值在 后续的 遍历中,将不会改变
* 所以,more 记录 右数组 最左边那个 value 的 index
*/
more = more == end ? i : more;
}
}
/**
* 左数组 或者 右数组 不存在
* 意味着 有半边不存在
* 那么 倒数子二个
* 就是下一个 大的 root 根节点
* 比如
* - 7
* - 4
* - 3 5
* - 2 6
* - 1
*
* 1 2 3 6 5 4 7
*
* 只有左边
* 下个大的 root 节点 就是 4
* 再次划分 1 2 3 6 5 4
* 划分之后 [1 2 3] [6 5] 4
*
* 然后继续递归
*
* 这是一种特殊情况
*/
if (less == -1 || more == end) {
return isPostOrderArrayOfBST(array, start, end - 1);
}
// 左右数组 不相邻,不是 BST 的后序遍历结构规则
if (less != more - 1) {
return false;
}
// 左右数组继续递归
return isPostOrderArrayOfBST(array, start, less) && isPostOrderArrayOfBST(array, more, end - 1);
}
public static void main(String[] args) {
Integer[] array = {1, 2, 3, 6, 5, 4, 9, 10, 8, 7};
IsPostOrderArrayOfBST integerIsPostOrderArrayOfBST = new IsPostOrderArrayOfBST();
System.out.println(integerIsPostOrderArrayOfBST.isPostOrderArrayOfBST(array));
}
}