1123 Is It a Complete AVL Tree（3

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

struct node
{
    int data;
    node *left;
    node *right;
};

node* leftRotate(node* input)
{
    node *temp = input->right;
    input->right = temp->left;
    temp->left = input;
    return temp;
}
node* rightRotate(node* input)
{
    node* temp = input->left;
    input->left = temp->right;
    temp->right = input;
    return temp;
}
node* rightleft(node* input)
{
    input->right = rightRotate(input->right);
    return leftRotate(input);
}
node* leftright(node* input)
{
    input->left = leftRotate(input->left);
    return  rightRotate(input);
}
int getHeight(node *input)
{
    if (input == NULL) return 0;
    int l = getHeight(input->left);
    int r = getHeight(input->right);
    return max(l, r) + 1;
}

node* inserttree(node* input,int a)//input表示原来的已经建立的树，a表示待插入的数
{
    if (input==NULL)//如果数空，则用该数值填充
    {
        input = new node;
        input->data = a;
    }
    else if (input->data > a)//如果插入节点的数小于根节点则递归插入左子树
    {
        input->left = inserttree(input->left, a);
        int l = getHeight(input->left), r = getHeight(input->right);
        if (l - r >= 2)
        {
            if (a < input->left->data)//如果该值小于左子树的值则右旋
            {
                input = rightRotate(input);
            }
            else
            {
                input = leftright(input);
            }
        }
    }
    else
    {
        input->right = inserttree(input->right, a);
        int l = getHeight(input->left), r = getHeight(input->right);
        if (r-l>=2)
        {
            if (a>input->right->data)
            {
                input = leftRotate(input);//插入的位置是右子树的右子树，则需要左旋即可
            }
            else
            {
                input = rightleft(input);
            }
        }
    }
    return input;
}

int isComplate = 1, after = 0;
vector<int> levelOrder(node *input)
{
    vector<int> v;
    queue<node *> iqueue;
    iqueue.push(input);
    while (!iqueue.empty())
    {
        node* temp = iqueue.front();
        iqueue.pop();
        v.push_back(temp->data);
        if (temp->left!=NULL)
        {
            if (after)
            {
                isComplate = 0;
            }
            iqueue.push(temp->left);
        }
        else
        {
            after = 1;
        }
        if (temp->right != NULL)
        {
            if (after) isComplate = 0;
            iqueue.push(temp->right);
        }
        else
        {
            after = 1;
        }
    }
    return v;
}

int main()
{
    int M, a;
    cin >> M;
    node* tree=nullptr;
    for (int i = 0; i < M; i++)
    {
        cin >> a;
        tree = inserttree(tree, a);
    }

    vector<int> v = levelOrder(tree);
    
    for (int i = 0; i < v.size(); i++)
    {
        if (i!=0)
        {
            cout << " ";
        }
        cout << v[i];
    }
    cout << endl;
    if (isComplate)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    system("pause");
    return 0;
}