OIer博客

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

解题思路

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

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

程序实现

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