Description:

将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。

Input:

输入第一行给出一个不超过20的正整数N；第二行给出N个互不相同的正整数，其间以空格分隔。

Output:

将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果，数字间以1个空格分隔，行的首尾不得有多余空格。第二行输出“YES”，如果该树是完全二叉树；否则输出“NO”。

Sample Input:

9
38 45 42 24 58 30 67 12 51

Sample Output:

38 45 24 58 42 30 12 67 51
YES

Sample Input:

8
38 24 12 45 58 67 42 51

Sample Output:

38 45 24 58 42 12 67 51
NO

题目链接

利用数组按照题目要求建立二叉树，最后层序遍历输出时判断是否为完全二叉树。
数组建立二叉树通过下标定位：

  • 若根节点下标为0：设节点下标为n，此节点左孩子下标为2n+1,右孩子下标为2n+2
  • 若根节点下标为1：设节点下标为n，此节点左孩子下标为2n,右孩子下标为2n+1

AC代码:

#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const double eps = 1e-5;
const double e = 2.718281828459;

int n, num;
// 二叉树数组
// 若根节点下标为0：设节点下标为n，此节点左孩子下标为2*n+1,右孩子下标为2*n+2
// 若根节点下标为1：设节点下标为n，此节点左孩子下标为2*n,右孩子下标为2*n+1
int tree[maxn];

// 根据题目要求递归建立二叉树
void Build_tree(int a) {
    // 若节点为空，则将数值放置在此
    if (tree[a] == -1) {
        tree[a] = num;
    }
    // 小于父节点在右侧寻找
    else if (num < tree[a]) {
        // 下标计算可以利用位运算
        Build_tree(a * 2 + 2);
    }
    // 大于在左侧寻找
    else {
        // 下标计算可以利用位运算
        Build_tree(a * 2 + 1);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    mem(tree, -1);
    for (int i = 0; i < n; ++i) {
        cin >> num;
        // 从根节点开始寻找数值应该插入位置
        Build_tree(0);
    }
    bool flag = 1;
    int cnt = 1;
    for (int i = 0; cnt <= n; ++i) {
        // 层序遍历中若出现空节点则不是完全二叉树，改变判断bool变量值
        if (tree[i] == -1) {
            flag = 0;
        }
        // 按照要求输出层序遍历结果
        else {
            if (cnt == n) {
                cout << tree[i] << endl;
            }
            else {
                cout << tree[i] << " ";
            }
            cnt++;
        }
    }
    // 根据判断是否为完全二叉树的bool变量输出结果
    if (flag) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
    return 0;
}