题解 | #二叉树遍历#

#include <iostream>
#include <math.h>
#include<bits/stdc++.h>

using namespace std;
struct Treenode{
    char val;
    Treenode*left;
    Treenode*right;
    Treenode(char c):val(c),left(NULL),right(NULL){};
};

Treenode* creattree(string preorder,string inorder){
    if(preorder.size()==0)return NULL;
    else{
    char c=preorder[0];
    Treenode *root=new Treenode(c);
    int position=inorder.find(c);
    root->left=creattree(preorder.substr(1,position),inorder.substr(0,position));
    root->right=creattree(preorder.substr(position+1),inorder.substr(position+1));
    return root;

    }

}

void houxu(Treenode*root){
    if(root==NULL)return;
    else{
        houxu(root->left);
        houxu(root->right);
        cout<<root->val;
    }
}

int main(){
    string preorder,inorder;
    while(cin>>preorder>>inorder){
        Treenode*root=creattree(preorder,inorder);
        houxu(root);
        cout<<endl;
    }

    return 0;
}