判断完全二叉树

1. 题目链接

天梯赛真题 -- 是否是完全二叉搜索树

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[21];

// 左子树大，右子树小
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, a[100];
typedef struct tree{
    int val;
    struct tree *left, *right;
}TreeNode, *Tree;
 
void add(Tree &t, int val)
{
    if(t == NULL)   
    {
        Tree s = new TreeNode;
        s->val = val;
        s->left = s->right = NULL;
        t = s;
    }
    else
    {
        if(val > t->val)    add(t->left, val);
        else add(t->right, val);
    }
}
 
void levelPrint(Tree &t)
{
    if(t == NULL)   return ;
    
    vector<int> v;
    queue<Tree> q;
    
    q.push(t);
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        v.push_back(t->val);
        if(t->left) q.push(t->left);
        if(t->right)    q.push(t->right);
    }
    
    for(int i = 0; i < v.size(); i ++ )
    {
        cout << v[i];
        if(i != v.size() - 1)   cout << " ";
    }
    cout << endl;
}
 
bool check(Tree &t)
{
    if(t == NULL)   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);
            while(q.size())
            {
                t = q.front();
                if(!t->left && !t->right)   q.pop();
                else    return false;
            }
            return true;
        }
    }
    return true;
}
 
int main()
{ 
    Tree t = NULL;
    cin >> n;
    for(int i = 0; i < n; i ++ )
    {
        int v;
        cin >> a[i];
    }
    for(int i = 0; i < n; i ++ )    add(t, a[i]);
    levelPrint(t);
    
    bool flag = check(t);
    if(flag)   cout << "YES" << endl;
    else    cout << "NO" << endl;
    return 0;
}