题解 | 二叉树遍历

#include <bits/stdc++.h>
using namespace std;

struct TNode{
    char data;
    struct TNode* left;
    struct TNode* right;
    TNode(char c):data(c),left(nullptr),right(nullptr){}
};

TNode* copBuild(string pre,string in){
    if(pre.size()==0)return nullptr;
    char core=pre[0];
    TNode* t=new TNode(core);
    int pos=in.find(core);
    t->left=copBuild(pre.substr(1,pos),in.substr(0,pos));
    t->right=copBuild(pre.substr(pos+1),in.substr(pos+1));
    return t;
}

void postOrder(TNode* t){
    if(t==nullptr)return;
    postOrder(t->left);
    postOrder(t->right);
    cout<<t->data;
}

int main(){
    string s1,s2;
    while(cin>>s1>>s2){
        TNode* t = copBuild(s1,s2);
        
        postOrder(t);
        cout<<endl;
    }
}

核心是构建过程的递归逻辑，我的习惯是根据先序遍历的特性去处理，先序遍历的每个分块的第一个，一定是根节点，那么他的左右节点就是根据下面的中序遍历的该节点的位置分割得到的子结构的第一个节点，那么这个递归逻辑就出来了，之后的操作都是一样的，那么就可以写成上述的结构，根据find函数找到位置，然后sub一下就可以轻松解决了