1. 题目链接

天梯赛真题 – 是否是完全二叉搜索树
下面的两种写法都是使用动态内存分配来建树的，当数据规模比较小时（一般在 $20$ 左右），是可以使用数组建树的。

2. 根据节点编号判断（better）

借鉴自这里

规定根节点的编号为 $1$，左孩子节点编号为 $left$，右孩子节点编号为 $right$，父节点的节点编号为 $fa$，则有：
$left=fa<<1$
$right=fa<<1|1$
由于完全二叉树的节点编号是递增的，因此它的最大的节点编号一定等于节点的个数。所以说，我们可以根据这一性质，简单的通过一个 $dfs$ 就可以判断是否是完全二叉树。

// 建立完全二叉树 + 判断二叉完全树
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 23;

typedef struct searchTree_t {
    int val;
    searchTree_t *left;
    searchTree_t *right;
    searchTree_t(int _val) : val(_val), left(nullptr), right(nullptr) {}
} Tree;

int n;
Tree *q[N];

// 左子树大，右子树小
void insert(Tree *&root, int x)
{
    if(root == nullptr)    
    {
        Tree *newNode = new Tree(x);
        root = newNode;
        return ;
    }
    if(x < root->val)  insert(root->right, x);
    else    insert(root->left, x);
}

Tree* init()
{
    Tree *root = nullptr;
    cin >> n;
    for(int i = 0; i < n; i ++ )
    {
        int x;  cin >> x;
        insert(root, x);
    }
    return root;
}

// 层次遍历
void bfs(Tree *root)
{
    if(root == nullptr) return ;
    int hh = 0, tt = -1;
    q[ ++ tt ] = root;
    while(hh <= tt)
    {
        auto t = q[ hh ++ ];
        if(t->left)     q[ ++ tt ] = t->left;
        if(t->right)    q[ ++ tt ] = t->right;
    }
    for(int i = 0; i < n; i ++ )
        cout << q[i]->val << " \n"[i == n - 1];
}

// dfs 得到最大的节点编号
int max_node;
void dfs(Tree *&root, int k)
{
    if(root == nullptr) return ;
    if(max_node > n)    return ;    // 剪枝 && 防溢出
    
    max_node = max(max_node, k);
    if(root->left)  dfs(root->left, k << 1);
    if(root->right) dfs(root->right, k << 1 | 1);
}

void solve()
{
    Tree *t = init();
    /*====== question1 ========*/
    bfs(t);
    /*====== question2 ========*/
    max_node = 1;
    dfs(t, 1);
    if(max_node == n) puts("YES");
    else    puts("NO");
}

int main()
{
    solve();
    return 0;
}

3. 根据完全二叉树的性质判断

看一下这里判断是否是完全二叉树在看一下上面的，高下立判了！
光从代码上看，上面的 $dfs$ 仅仅 $11$ 行，而下面的类似于“模拟”用了 $30$ 行，并且代码量大就意味着，出错了不好调 $bug$，理解不深刻的话还可能写不出来等等问题。
不过，这种方法仍然值得掌握！

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
 
using namespace std;
 
int n;
typedef struct searchTree_t {
    int val;
    searchTree_t *left;
    searchTree_t *right;
    searchTree_t(int _val) : val(_val), left(nullptr), right(nullptr) {}
}TreeNode, *Tree;

void insert(Tree &t, int val)
{
    if(t == nullptr)   
    {
        t = new TreeNode(val);
        return ;
    }
    if(val > t->val)    insert(t->left, val);
    else insert(t->right, val);
}

Tree init()
{
    Tree t = nullptr;
    cin >> n;
    for(int i = 0; i < n; i ++ )    
    {
        int x;  cin >> x;
        insert(t, x);
    }
    return t;
}
 
void bfs(Tree &t)
{
    if(t == nullptr)   return ;
    
    vector<int> res;
    queue<Tree> q;
    q.push(t);
    while(q.size())
    {
        auto t = q.front(); q.pop();
        res.push_back(t->val);
        if(t->left)     q.push(t->left);
        if(t->right)    q.push(t->right);
    }

    int len = res.size();
    for(int i = 0; i < len; i ++ )
        cout << res[i] << " \n"[i == len - 1];
}
 
bool check(Tree &t)
{
    // 规定空树不是完全二叉树
    if(t == nullptr)   return false;
    
    queue<Tree> q;
    q.push(t);
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        // 在完全二叉树中，某个节点如果有右子树，就必须有左子树
        if(t->left && t->right)
        {
            q.push(t->left);
            q.push(t->right);
        }
        else if(!t->left && t->right)   return false;
        else if(!t->right)
        {
            if(t->left) q.push(t->left); // 别忘了也将这个点加入队列
            // 因为我们这里相当于做了 bfs
            // 此时队列中的点为应该为 t 同层的所有右侧节点和下一层的所有节点
            // 而这些点应该都是叶子节点！
            while(q.size())
            {
                t = q.front();
                if(!t->left && !t->right)   q.pop();
                else    return false;
            }
        }
    }
    // 前面都没检查出问题，确实是一颗完全二叉树
    return true;
}

void solve()
{
    Tree t = init();
    /*====== question1 ======*/
    bfs(t);
    /*====== question2 ======*/
    if(check(t))   cout << "YES" << endl;
    else    cout << "NO" << endl;
}
 
int main()
{ 
    solve();
    return 0;
}

4. 二叉树补充题目

判断是否是完全二叉树
二叉搜索树增删查找