题解 | #二叉树遍历#

#include<bits/stdc++.h>
using namespace std;
struct TreeNode{
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char c):data(c), left(NULL), right(NULL){}
};
void builTree(TreeNode* &root, string prestr, string instr){
    //递归终止条件
    if(prestr.empty())return ;
    //继续递归
    root = new TreeNode(prestr[0]);//生成新结点
    prestr.erase(0, 1);
    string prestr_l = "";//左子树的前序序列
    string prestr_r = "";//右子树的前序序列
    string instr_l = "";//左子树的中序序列
    string instr_r = "";//右子树的中序序列
    int flag = 0;//0为左子树 1为右子树
    for(int i = 0; i < instr.size(); i++){//统计左右子树的前序 中序序列
        if(instr[i] == root->data)flag = 1;
        else if(flag == 0){
            instr_l += instr[i];
            prestr_l += prestr[i];
        }else if(flag == 1){
            instr_r += instr[i];
            prestr_r += prestr[i-1];
        }
    }
    builTree(root->left, prestr_l, instr_l);
    builTree(root->right, prestr_r, instr_r);
}
void postOrder(TreeNode* root){
    if(root == NULL)return ;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->data;
}
int main(){
    string prestr = "";
    string instr = "";
    TreeNode* tree = NULL;
    while(cin >> prestr >> instr){
        delete tree;
        tree = NULL;
        /*
            前序构造二叉树:
            当前子树的前序序列第一个元素为子树根节点，生成新节点，
            当前子树的中序序列可以分出根节点的左右子树，
            递归下去
        */
        //构造二叉树
        builTree(tree, prestr, instr);
        //后序遍历输出
        postOrder(tree);
        cout << endl;
    }
    return 0;
}