剑指offer面试题24-二叉搜寻树的后序遍历序列

剑指offer面试题24-二叉搜索树的后序遍历序列

题目：

/*
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后续遍历的结果。<br/>
 * 如果是则返回true，否则返回false。<br/>
 * 假设输入的数组的任意两个数组都互不相同
 * */

既然是后序遍历，那么根元素肯定是在最后一个。

又应该为二叉搜索树，所以左边一半的肯定比根要小，右边一半的比根要大。

现在有了根，就可以把剩下的数组根据比根小与比根大的分割线分成两半。

然后再递归判断。

什么时候返回false：

当确定了某个分割点以后，（左边的全比根小，右边的第一个比根大）又在右边的数组中找到一个比根小的，说明该数组不满足二叉搜索树的后序遍历。

package com.aii.algorithm;

/**
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后续遍历的结果。<br/>
 * 如果是则返回true，否则返回false。<br/>
 * 假设输入的数组的任意两个数组都互不相同
 * */
public class VerifySquenceOfBST {

	public boolean check(int[] array, int start, int end) {
		if (end >= 0 && end - start <= 1) {
			return true;
		}
		int root = array[end];
		int newRootIndex = -1;

		// 1.找出那个分割线
		for (int i = start; i < end; i++) {
			// 遇到比root大的数，表示前一半已找到。
			// 则前一半的根原始的i-1
			if (array[i] > root) {
				newRootIndex = i;
				break;
			}
		}

		// 2.确定分割线以后再看左边和右边是否都满足，最后是用left&&right判断
		boolean left = true;
		boolean right = true;

		// newRootIndex=-1没找到，进这个if说明是找到了
		if (newRootIndex != -1) {

			// 现在要做的就是验证后半部分是否都满足所有的元素都大于root
			for (int i = newRootIndex; i < end - 1; i++) {
				// 如果找到一个，那就肯定是不满足的了，返回false
				if (array[i] < root) {
					return false;
				}
			}

			// 如果要找check(array,start,newRootIndex-1)，则必须保证end比start要大，
			// 即newRootIndex-1 - start > 0
			if (newRootIndex - 1 - start > 0) {
				left = check(array, start, newRootIndex - 1);
			}

			// 如果要找check(array,newRootIndex,end-1),则必须保证end-1比newRootIndex要大
			// 即end-1 - newRootIndex > 0
			if (end - 1 - newRootIndex > 0) {
				right = check(array, newRootIndex, end - 1);
			}

		} else {
			// 遇到没有找到的起概况，那就说明所有的数都比root小，那全在root的左节点下，
			// 所以left=check(array,start,end-1)
			left = check(array, start, end - 1);
		}
		return left && right;
	}
}