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

无情 阅读:397 2020-10-21 17:21:52 评论:0

题目描述

输入一个非空整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出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); 
} 

  

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
KIKK导航

KIKK导航

排行榜
关注我们

一个IT知识分享的公众号