当前位置:首页 > 数据结构 > 二叉树 > 正文
GDKOI2021普及组Day2B二叉树
1091+

题目大意:给定一个二叉搜索树的广搜序列,请问他是不是完满二叉树?结点数位n,结点是n的一个排列。

解题思路

首先,他们告诉我们他是一颗二叉搜索树的BFS序,我们可以按照这个序列建树。

因为他是BFS序,所以我们建立二叉搜索树,每次进去的结点都是深度最大的,可以唯一确定一棵树。建立二叉搜索树后,再验证BFS序和结点的度即可。(有超时风险)

程序实现

以下程序则是按照BFS序建树,再判断是否二叉搜索树。首先第一个结点是根节点,接下来两个两个读入左儿子和右儿子。显然,只能找到唯一一个父亲结点,如果出现两个符合搜索树要求的父亲,肯定怎么放都是不合法的。所以,只要答案是YES,建立的二叉树肯定也是唯一的。最后颜色中序遍历是否1到n即可。查找父亲时用双指针维护,每次验证的时间复杂度都是O(n)的。

GDKOI2021普及组Day2B二叉树:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!