二叉搜索树的后序遍历序列

原创
2016/08/17 11:21
阅读数 40
  • 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
//大致的思路就是在分割点前后的分别是小于以及大于pivot的
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0)
            return false;
    	return VerifyBST(sequence, 0, sequence.length - 1);    
    }
    
    private boolean VerifyBST(int[] seq, int start, int end) {
		if (end - start <= 1)
			return true;
		int midVal = seq[end];
		int pivot = start;
		int mid;
		while (seq[pivot] < midVal)
			pivot++;
		mid = pivot;
		while (pivot != end) {
			if (seq[pivot++] < midVal)
				return false;
		}
		return VerifyBST(seq, start, mid - 1) && VerifyBST(seq, mid, end - 1);
	}
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部