PAT甲题题解-1102. Invert a Binary Tree (25)-（建树，水题）

　　就是把输入给的左孩子右孩子互换一下，然后输出层次遍历和中序遍历。

#include <iostream>

#include <algorithm>

#include <cstring>

#include <string.h>

#include <cstdio>

#include <queue>

using namespace std;

const int maxn=;

bool first=true;

struct Node{

    int id;

    int left;

    int right;

}node[maxn];

int vis[maxn]; //没出现的即是根节点

//层次遍历

void level_order(int i){

    queue<Node>q;

    q.push(node[i]);

    Node tmp;

    while(!q.empty()){

        tmp=q.front();

        q.pop();

        if(first){

            first=false;

            printf("%d",tmp.id);

        }

        else

            printf(" %d",tmp.id);

        int l=tmp.left;

        int r=tmp.right;

        if(l!=-)

            q.push(node[l]);

        if(r!=-)

            q.push(node[r]);

    }

}

//中序遍历

void in_order(int i){

    if(i==-)

        return;

    int l=node[i].left;

    int r=node[i].right;

    in_order(l);

    if(first){

        printf("%d",i);

        first=false;

    }

    else{

        printf(" %d",i);

    }

    in_order(r);

}

int main()

{

    int n;

    char str1[],str2[];

    memset(vis,,sizeof(vis));

    scanf("%d",&n);

    for(int i=;i<n;i++){

        scanf("%s %s",str1,str2);

        node[i].id=i;

        if(str1[]=='-')

            node[i].right=-;

        else{

            node[i].right=str1[]-'';

            vis[str1[]-'']=;

        }

        if(str2[]=='-')

            node[i].left=-;

        else{

            node[i].left=str2[]-'';

            vis[str2[]-'']=;

        }

    }

    int root;

    for(int i=;i<n;i++){

        if(!vis[i]){

            root=i;

            break;

        }

    }

    first=true;

    level_order(root);

    printf("\n");

    first=true;

    in_order(root);

    return ;

}