题解 | #二叉树遍历#

#include <iostream>
#include<string>
#include<cstring>
#include<cstdio>
using namespace std;
typedef struct Binode {
    char data;
    struct Binode* lnode;
    struct Binode* rnode;
    Binode(char c): data(c), lnode(NULL), rnode{NULL} {}
};
Binode* midVisit(string prestr, string midstr) {

    if (prestr.size() == 0) return NULL;
    char root = prestr[0];
//    cout<<"\n当前根节点为："<<root;

    Binode* b = new Binode(root);
    int position = midstr.find(root);
    b->lnode = midVisit(prestr.substr(1, position), midstr.substr(0, position));
    b->rnode = midVisit(prestr.substr(position + 1),
                        midstr.substr(position +
                                      1)); //敲成midstr.substr(position)会闪退,因为substr找不到对应的position
//                string mid1="                            ";
//                string mid2="                            ";
//                for(int j=0;j<i;j++){
//                   if(midstr[j]==NULL||midstr[j]==' ') break;
//                     mid1[j]=midstr[j];
//
//                }
//                cout<<"\n左字符串为"<<mid1;
//                b->lnode= midVisit(prestr,mid1,pos);
//                for(int k=i+1,m=0;k<midstr.size();k++,m++){
//                    if(midstr[k]==NULL||midstr[k]==' ') break;
//
//                    mid2[m]=midstr[k];
//                }
//                 cout<<"\n右字符串为"<<mid2;
//                   b->rnode= midVisit(prestr,mid2,pos);
    return b;
}

//后续遍历
void lastVist(Binode* b) {
    if (b == NULL) return;
    lastVist(b->lnode);
    lastVist(b->rnode);
    cout << b->data;
}
int main() {
    string strpre, strmid;
    while (cin >> strpre >> strmid) {
        //遍历前序，找根
        Binode* res = midVisit(strpre, strmid);
        lastVist(res);
//        string strtest="kkkkk";
//        int testpos=strtest.find('a');
//        string strtestres=strtest.substr(testpos);//闪退
    }
    return 0;
}