package algorithm;
public class BinarySearchTreePostOrder {
/**
* 二叉搜索树的后序遍历序列
* <p>
* 首先要拿到数组末尾即使二叉树根节点，因为是搜索树，所以左子树比根节点小，右子树都比根节点大。
* 若发现异常即不是后序遍历序列。
* <p>
* 1. 因为左子树和右子树都符合以上规律，所以用递归方法；为避免创建新的子树序列数组，需要创建一个新函数，传入start,end
* 2. 遍历数组，找到值比根节点大的节点，即为左子树和右子树的分界坐标
* 3. 分界后继续用递归检查是否合法
*
* @param postOrder 序列数组
* @return 序列是否合法
*/
public static boolean isPostOrder(int[] postOrder) {
if (postOrder == null || postOrder.length <= 0) return false;
int len = postOrder.length;
int start = 0;
// 这里传入end是(len - 1)，因为数组的len比数组下标大1
return isPostOrder(postOrder, start, len - 1);
}
public static boolean isPostOrder(int[] postOrder, int start, int end) {
if (start >= end) return true;
// 取最后一个，即是根节点
int root = postOrder[end];
int i = start;
for (; i < end; i++) {
// 如果大于节点，则直接break，已记录下的就是左子树和右子树的分界坐标
if (postOrder[i] >= root) {
break;
}
}
int j = i;
for (; j < end; j++) {
if (postOrder[j] <= root) {
return false;
}
}
return isPostOrder(postOrder, start, i - 1) && isPostOrder(postOrder, i, end - 1);
}
public static void main(String[] args) {
int[] a = {5, 7, 6, 9, 11, 10, 8};
int[] b = {7, 4, 6, 5};
boolean is = isPostOrder(a);
boolean isB = isPostOrder(b);
System.out.println("isPostOrder = " + is);
System.out.println("isPostOrder = " + isB);
}
}
二叉搜索树的后序遍历序列-Java
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 题目:输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的...
- 题目 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的...
- 题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的...
