二叉搜索树的后序遍历序列算法详解编程语言

//每次都找左右树的分界点，然后判断 
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); 
}