为啥会输出一个空格???
查看原帖
为啥会输出一个空格???
365433
Mark_M楼主2022/8/12 13:45
#include <bits/stdc++.h>
using namespace std;
string pre,in;
struct TNode
{
    char data;
    TNode *lchild,*rchild;
    TNode(){
        lchild = rchild = nullptr;
    }
    TNode(char d,TNode *l,TNode *r){
        data = d;
        lchild = l;
        rchild = r;
    }
};
TNode *Build(TNode *node,int PL,int PR,int IL,int IR){
    if(PL>=PR){
        node = new TNode(pre[PL],nullptr,nullptr);
        return node;
    }
    char root_val = pre[PL];
    int p;
    for(int i=IL;i<=IR;i++){
        if(in[i]==root_val){
            p = i;
            break;
        }
    }
    int lc = p - IL;
    int rc = IR - p;
    node = new TNode(root_val,nullptr,nullptr);
    node->lchild = Build(node->lchild,PL+1,PL+lc,IL,p-1);
    node->rchild = Build(node->rchild,PL+lc+1,PR,p+1,IR);
    return node;
}

void PostTraverse(TNode *root)
{
    if(root==nullptr) return;
    PostTraverse(root->lchild);
    PostTraverse(root->rchild);
    cout<<root->data;
}
int main(){
    cin>>in>>pre;
    int prelen=pre.length(),inlen=in.length();
    TNode *root=nullptr;
    root=Build(root,0,prelen-1,0,inlen-1);
    PostTraverse(root);
    return 0;
}
2022/8/12 13:45
加载中...