【PAT】1102 Invert a Binary Tree (25 分)

【PAT】1102 Invert a Binary Tree (25 分)

①输入的时候就左右子树互换，不用之后再递归互换了 

②递归左右互换

#include 
#include 
#include 
#include 
using namespace std;
struct node
{
    int lchild,rchild;
};

vector T;
int times[15];

int flag_levelOrder=0;
void levelOrderTraversal(int root){
    if(root==-1) return;
    queue q;
    q.push(root);
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        printf("%s%d",flag_levelOrder==1?" ":"",tmp);
        flag_levelOrder=1;
        if(T[tmp].lchild!=-1) q.push(T[tmp].lchild);
        if(T[tmp].rchild!=-1) q.push(T[tmp].rchild);
    }
    printf("n");
}

int flag_inOrder=0;
void inOrderTraversal(int root){
    if(root==-1) return;
    inOrderTraversal(T[root].lchild);
    printf("%s%d",flag_inOrder==1?" ":"",root);
    flag_inOrder=1;
    inOrderTraversal(T[root].rchild);
}

int main(){
    int n;
    scanf("%d",&n);
    T.resize(n);

    string t1,t2;
    for(int i=0;i>t2>>t1;
        if(t1=="-"){
            T[i].lchild=-1;
        }else{
            T[i].lchild=stoi(t1);
            times[stoi(t1)]=1;
        }
        if(t2=="-"){
            T[i].rchild=-1;
        }else{
            T[i].rchild=stoi(t2);
            times[stoi(t2)]=1;
        }
    }

    int root=0;
    while(times[root]==1) root++;

    levelOrderTraversal(root);
    inOrderTraversal(root);

    return 0;
}

#include 
#include 
#include 
#include 
using namespace std;
struct node
{
    int lchild,rchild;
};

vector T;
int times[15];

void invertRoot(int root){
    if(root==-1) return;
    //不管有没有子树都可以直接交换
    int t=T[root].lchild;
    T[root].lchild=T[root].rchild;
    T[root].rchild=t;
    
    invertRoot(T[root].lchild);
    invertRoot(T[root].rchild);
}

int flag_levelOrder=0;
void levelOrderTraversal(int root){
    if(root==-1) return;
    queue q;
    q.push(root);
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        printf("%s%d",flag_levelOrder==1?" ":"",tmp);
        flag_levelOrder=1;
        if(T[tmp].lchild!=-1) q.push(T[tmp].lchild);
        if(T[tmp].rchild!=-1) q.push(T[tmp].rchild);
    }
    printf("n");
}

int flag_inOrder=0;
void inOrderTraversal(int root){
    if(root==-1) return;
    inOrderTraversal(T[root].lchild);
    printf("%s%d",flag_inOrder==1?" ":"",root);
    flag_inOrder=1;
    inOrderTraversal(T[root].rchild);
}

int main(){
    int n;
    scanf("%d",&n);
    T.resize(n);

    string t1,t2;
    for(int i=0;i>t1>>t2;
        if(t1=="-"){
            T[i].lchild=-1;
        }else{
            T[i].lchild=stoi(t1);
            times[stoi(t1)]=1;
        }
        if(t2=="-"){
            T[i].rchild=-1;
        }else{
            T[i].rchild=stoi(t2);
            times[stoi(t2)]=1;
        }
    }

    int root=0;
    while(times[root]==1) root++;

    invertRoot(root);

    levelOrderTraversal(root);
    inOrderTraversal(root);

    return 0;
}