每日一题(L2-011):玩转二叉树--建树+层序遍历

与L2-006近乎相同，先建树，然后遍历

#include<bits/stdc++.h>
using namespace std;
int in[35];
int pre[35];
typedef struct Tree{
    int num;
    Tree* left;
    Tree* right;
}T;

T * build(int in1,int in2,int pre1,int pre2){
    T * t=new T;
    t->num=pre[pre1];
    int key=pre[pre1];
    int i=0;
    for(i=in1;i<=in2;i++){
        if(in[i]==key){
        break;
        }
    }
    int num_node=i-in1;
    if(i!=in1){
    t->left=build(in1,i-1,pre1+1,pre1+num_node);
    }
    if(i!=in2){
    t->right=build(i+1,in2,pre1+num_node+1,pre2);
    }
    return t;
}
void visit(T * t){
    if(t == NULL){
        return ;
    }
    queue<T*> q;
    q.push(t);
    while(!q.empty()){
        T* tt=q.front();
        cout<<tt->num;
        if(tt->right  != NULL){
           q.push(tt->right);
        }
        if(tt->left  != NULL){
           q.push(tt->left);
        }
        q.pop();
        if(!q.empty()){
            cout<<' ';
        }
    }
    
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
    cin>>in[i];
    }
    for(int i=0;i<n;i++){
    cin>>pre[i];
    }
    T * root=build(0,n-1,0,n-1);
    visit(root);
    return 0;
}