C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-10-31

#include<iostream>
#include<vector>
using namespace std;


struct Tree{
    int val;
    Tree *left, *right;
    Tree(int val):val(val), left(NULL), right(NULL){}
};
 
Tree *Build(vector<int> level, vector<int> in, int s, int e){
    if(level.empty())
        return NULL;
    Tree *T = new Tree(level[0]);
    vector<int> l, r;
    int k=s;
    bool isleft;
    while(in[k]!=level[0])
        k++;
    for(int i=1;i<level.size();i++){
        isleft = false;
        for(int j=s;j<k;j++){
            if(level[i]==in[j]){
                isleft = true;
                break;
            }
        }
        if(isleft)
            l.push_back(level[i]);
        else
            r.push_back(level[i]);
    }
    T->left = Build(l, in, s, k-1);
    T->right = Build(r, in, k+1, e);
    return T;
}
 
void Leaves(Tree *T, vector<int> &leaf){
    if(!T)
        return;
    if(T->left==NULL && T->right==NULL){
        leaf.push_back(T->val);
        return;
    }
    Leaves(T->left, leaf);
    Leaves(T->right, leaf);
}
 
void PreOrder(Tree *T, vector<int> &pre){
    if(!T)
        return;
    pre.push_back(T->val);
    PreOrder(T->left, pre);
    PreOrder(T->right, pre);
}
 
void PostOrder(Tree *T, vector<int> &post){
    if(!T)
        return;
    PostOrder(T->left, post);
    PostOrder(T->right, post);
    post.push_back(T->val);
}
 
void Print(vector<int>& v){
    for(int i=0;i<v.size();i++){
        if(i==v.size()-1)
            cout<<v[i]<<endl;
        else
            cout<<v[i]<<" ";
    }
}
 
int main(){
    vector<int> a, b;
    int x;
    while(cin>>x){
        a.push_back(x);
        if(getchar()=='\n')
            break;
    }
    while(cin>>x){
        b.push_back(x);
        if(getchar()=='\n')
            break;
    }
    Tree *T = Build(a, b, 0, b.size()-1);
    vector<int> pre, post, leaf;
    Leaves(T, leaf);
    Print(leaf);
    PreOrder(T, pre);
    Print(pre);
    PostOrder(T, post);
    Print(post);
       return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-07-27

#include<iostream>
#include<vector>
using namespace std;


struct Tree{
    int val;
    Tree *left, *right;
    Tree(int val):val(val), left(NULL), right(NULL){}
};
 
Tree *Build(vector<int> level, vector<int> in, int s, int e){
    if(level.empty())
        return NULL;
    Tree *T = new Tree(level[0]);
    vector<int> l, r;
    int k=s;
    bool isleft;
    while(in[k]!=level[0])
        k++;
    for(int i=1;i<level.size();i++){
        isleft = false;
        for(int j=s;j<k;j++){
            if(level[i]==in[j]){
                isleft = true;
                break;
            }
        }
        if(isleft)
            l.push_back(level[i]);
        else
            r.push_back(level[i]);
    }
    T->left = Build(l, in, s, k-1);
    T->right = Build(r, in, k+1, e);
    return T;
}
 
void Leaves(Tree *T, vector<int> &leaf){
    if(!T)
        return;
    if(T->left==NULL && T->right==NULL){
        leaf.push_back(T->val);
        return;
    }
    Leaves(T->left, leaf);
    Leaves(T->right, leaf);
}
 
void PreOrder(Tree *T, vector<int> &pre){
    if(!T)
        return;
    pre.push_back(T->val);
    PreOrder(T->left, pre);
    PreOrder(T->right, pre);
}
 
void PostOrder(Tree *T, vector<int> &post){
    if(!T)
        return;
    PostOrder(T->left, post);
    PostOrder(T->right, post);
    post.push_back(T->val);
}
 
void Print(vector<int>& v){
    for(int i=0;i<v.size();i++){
        if(i==v.size()-1)
            cout<<v[i]<<endl;
        else
            cout<<v[i]<<" ";
    }
}
 
int main(){
    vector<int> a, b;
    int x;
    while(cin>>x){
        a.push_back(x);
        if(getchar()=='\n')
            break;
    }
    while(cin>>x){
        b.push_back(x);
        if(getchar()=='\n')
            break;
    }
    Tree *T = Build(a, b, 0, b.size()-1);
    vector<int> pre, post, leaf;
    Leaves(T, leaf);
    Print(leaf);
    PreOrder(T, pre);
    Print(pre);
    PostOrder(T, post);
    Print(post);
       return 0;
}