PTA A1123

AVL模版題+判斷是否是層序周遊

//
//  main.cpp
//  test6
//
//  Created by Jacky Roth on 2019/2/28.
//  Copyright © 2019 Jacky Roth. All rights reserved.
//
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace  std;
int N;
struct tree {
    int data,hight;
    tree* lchild;
    tree* rchild;
};

tree* creat_node(int x){
    tree* root=new tree();
    root->data=x;
    root->lchild=NULL;
    root->rchild=NULL;
    root->hight=1;
    return root;
}

int get_h(tree* root){
    if (root==NULL) {
        return 0;
    }
    return root->hight;
}

void updateh(tree* root){
    root->hight=max(get_h(root->lchild), get_h(root->rchild))+1;
}

int get_balance(tree* root){
    return get_h(root->lchild)-get_h(root->rchild);
}

void L(tree* &root){
    tree* temp=root->rchild;
    root->rchild=temp->lchild;
    temp->lchild=root;
    updateh(root);
    updateh(temp);
    root=temp;
}

void R(tree* &root){
    tree* temp=root->lchild;
    root->lchild=temp->rchild;
    temp->rchild=root;
    updateh(root);
    updateh(temp);
    root=temp;
}

void creat_tree(tree* &root,int data){
    if (root==NULL) {
        root=creat_node(data);
        return;
    }
    if (data<root->data) {
        creat_tree(root->lchild, data);
        updateh(root);
        if (get_balance(root)==2) {
            if (get_balance(root->lchild)==1) {
                R(root);
            }else{
                L(root->lchild);
                R(root);
            }
        }
    }else{
        creat_tree(root->rchild, data);
        updateh(root);
        if (get_balance(root)==-2) {
            if (get_balance(root->rchild)==-1) {
                L(root);
            }else{
                R(root->rchild);
                L(root);
            }
        }
    }
}

bool level(tree* root){
    bool tag=1;
    queue<tree*>q;
    tree* top;
    q.push(root);
    while (!q.empty()) {
        top=q.front();
        q.pop();
        if (!top) {
            break;
        }
        printf("%d",top->data);
        if (--N) {
            printf(" ");
        }
        q.push(top->lchild);
        q.push(top->rchild);
    }
    while (!q.empty()) {
        top=q.front();
        q.pop();
        if (top) {
            tag=0;
            printf("%d",top->data);
            if (--N) {
                printf(" ");
            }
            if (top->lchild) {
                q.push(top->lchild);
            }
            if (top->rchild) {
                q.push(top->rchild);
            }
        }
    }
    printf("\n");
    return tag;
}

int main(int argc, const char * argv[]) {
    int data;
    tree* root=NULL;
    scanf("%d",&N);
    for (int i=0; i<N; i++) {
        scanf("%d",&data);
        creat_tree(root, data);
    }
    if (level(root)) {
        printf("YES\n");
    }else{
        printf("NO\n");
    }
    return 0;
}