题目描述

输入一个非空整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
 
//每次都找左右树的分界点,然后判断 
bool judge(vector<int> sequence, int i_start, int i_end) 
{ 
	if (i_start-i_end>=0) 
	{ 
		return true; 
	} 
	int i_root = sequence[i_end]; 
	int index = i_start; 
	for (;index<i_end;index++) 
	{ 
		//找到分界点,左侧数都小于根节点 
		if (sequence[index]>i_root) 
		{ 
			break; 
		} 
	} 
 
	//判断右侧 
	for (int i_r_index=index;i_r_index<i_end;i_r_index++) 
	{ 
		if (sequence[i_r_index]<i_root) 
		{ 
			return false; 
		} 
	} 
 
	//再分别遍历左右子树判断 
	return judge(sequence, i_start, index-1) && judge(sequence, index, i_end - 1); 
} 
bool VerifySquenceOfBST(vector<int> sequence) { 
	if (sequence.size() == 0) 
		return false; 
	return judge(sequence, 0, sequence.size() - 1); 
} 

  

发布评论
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

LRU缓存机制讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。