【PAT甲级】1123 Is It a Complete AVL Tree

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：PAT题解集合
📝原题地址：题目详情 - 1123 Is It a Complete AVL Tree (pintia.cn)
🔑中文翻译：判断完全 AVL 树
📣专栏定位：为想考甲级PAT的小伙伴整理常考算法题解，祝大家都能取得满分！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

1123 Is It a Complete AVL Tree

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

Now given a sequence of insertions, you are supposed to output the level-order traversal sequence of the resulting AVL tree, and to tell if it is a complete binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤ 20). Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, insert the keys one by one into an initially empty AVL tree. Then first print in a line the level-order traversal sequence of the resulting AVL tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line. Then in the next line, print YES if the tree is complete, or NO if not.

Sample Input 1:

5
88 70 61 63 65

Sample Output 1:

70 63 88 61 65
YES

Sample Input 2:

8
88 70 61 96 120 90 65 68

Sample Output 2:

88 65 96 61 70 90 120 68
NO

题意

AVL 树是一种自平衡二叉搜索树。

在 AVL 树中，任何节点的两个子树的高度最多相差 1 个。

如果某个时间，某节点的两个子树之间的高度差超过 1 ，则将通过树旋转进行重新平衡以恢复此属性。

现在，给定插入序列，请你输出得到的 AVL 树的层序遍历，并判断它是否是完全二叉树。

思路

这道题其实就是对平衡二叉树的构建和判断是否为完全二叉树的结合，我们分两部分进行讲解。

首先，平衡二叉树失衡主要分为四种情况，下面讨论的是导致失衡前最后插入的一个结点位置：

1. 插入的结点在失衡结点的左孩子的左子树，直接右旋失衡结点。
2. 插入的结点在失衡结点的左孩子的右子树，先对失衡结点的左孩子进行左旋，再对失衡结点右旋。
3. 插入的结点在失衡结点的右孩子的右子树，直接左旋失衡结点。
4. 插入的结点在失衡结点的右孩子的左子树，先对失衡结点的右孩子进行右旋，再对失衡结点左旋。

其次，再来看看该如何判断是否为完全二叉树：

1. 我们可以利用完全二叉树的性质，用一个一维数组来存储，如果当前结点第下标为 k （假设下标从 1 开始），则满足以下条件：
   • 该结点的左孩子下标为 k * 2
   • 该结点的右孩子下标为 k * 2 + 1
2. 所以如果一个二叉树是完全二叉树的话，将它所有结点按上述方式存储到一维数组中是可以刚好填满 $1\sim N$（下标从 $1$ 开始）个位置的。相反如果不是完全二叉树，则 $1\sim N$ 个位置中会有空余，也就是说最后一个结点的位置会大于 $N$ 。故我们只用判断最后一个结点的位置是否为 $N$ 即可，如果是 $N$ 则说明是完全二叉树。
3. 最后输出判断结果，注意如果是完全二叉树还需要输出最后一个结点的编号，否则输出该树的根结点编号。

我们拿题目的第一个样例举例，可以得到下面这颗完全二叉树：

其在一维数组中的存储情况为：

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 25;
int n;
int l[N], r[N], h[N], v[N], idx;
int q[N], pos[N];

//更新当前结点的深度
void update(int u)
{
    h[u] = max(h[l[u]], h[r[u]]) + 1;
}

//右旋
void R(int& u)
{
    int p = l[u];
    l[u] = r[p], r[p] = u;
    update(u), update(p);
    u = p;
}

//左旋
void L(int& u)
{
    int p = r[u];
    r[u] = l[p], l[p] = u;
    update(u), update(p);
    u = p;
}

//获取左右结点深度之差
int get_balance(int u)
{
    return h[l[u]] - h[r[u]];
}

//插入结点
void insert(int& u, int w)
{
    if (!u)  u = ++idx, v[u] = w;
    else if (w < v[u])
    {
        insert(l[u], w);
        if (get_balance(u) == 2)
        {
            //如果插入结点在失衡结点的左孩子的左子树，则对失衡结点右旋
            if (get_balance(l[u]) == 1)   R(u);
            //如果插入结点在失衡结点的左孩子的右子树，则先对左孩子左旋，再对失衡结点右旋
            else    L(l[u]), R(u);
        }
    }
    else
    {
        insert(r[u], w);
        if (get_balance(u) == -2)
        {
            //如果插入结点在失衡结点的右孩子的右子树，则对失衡结点左旋
            if (get_balance(r[u]) == -1)   L(u);
            //如果插入结点在失衡结点的右孩子的左子树，则先对右孩子右旋，再对失衡结点左旋
            else    R(r[u]), L(u);
        }
    }

    update(u);	//更新当前结点的深度
}

//判断是否是完全二叉树
bool bfs(int root)
{
    int hh = 0, tt = 0;
    q[0] = root;
    pos[root] = 1;

    bool res = true;
    while (hh <= tt)
    {
        int t = q[hh++];

        if (pos[t] > n)    res = false;

        if (l[t])   q[++tt] = l[t], pos[l[t]] = pos[t] * 2;
        if (r[t])   q[++tt] = r[t], pos[r[t]] = pos[t] * 2 + 1;
    }

    return res;
}

int main()
{
    cin >> n;

    int root = 0;
    for (int i = 0; i < n; i++)
    {
        int w;
        cin >> w;
        insert(root, w);
    }

    bool res = bfs(root);

    cout << v[q[0]];
    for (int i = 1; i < n; i++)    cout << " " << v[q[i]];
    cout << endl;

    if (res)    puts("YES");
    else    puts("NO");

    return 0;
}