题解 | #二叉树遍历#

//递归的灵活运用
#include <iostream>
using namespace std;


struct TreeNode
{
    char data;
    TreeNode* leftchild;
    TreeNode* rightchild;
    TreeNode(char c): data(c),leftchild(NULL),rightchild(NULL){}
};

TreeNode* Build(string strq,string strz)
{
    if(strq.size()==0)return NULL;//该子树为空
    
    char c=strq[0];
    int position=strz.find(c);
    TreeNode* root=new TreeNode(c);
    root->leftchild=Build(strq.substr(1,position),strz.substr(0,position));
    root->rightchild=Build(strq.substr(position+1),strz.substr(position+1));

    return root;
}
void PostOrder(TreeNode* root)
{
    if(root==NULL)return;

    PostOrder(root->leftchild);
    PostOrder(root->rightchild);
    cout<<root->data;
}

int main() {
    string strq, strz;
    while (cin >> strq >> strz) {
        TreeNode* root=Build(strq,strz);
        PostOrder(root);
        cout<<endl;
    }
}