题解 | #二叉树遍历#

#include <iostream>
#include <string>
using namespace std;

struct TreeNode{
    char data;
    TreeNode * left;
    TreeNode * right;
};

TreeNode * rebuild(string pre, string med){
    if(pre.size()==0)
    {return NULL;}
    else{
        char root = pre[0];
        TreeNode *pNewNode = new TreeNode;
        pNewNode->data = root;
        int position = med.find(root);
        pNewNode->left = rebuild(pre.substr(1,position),med.substr(0,position));
        pNewNode->right = rebuild(pre.substr(position+1),med.substr(position+1));
        return pNewNode;
    }
}
void postOrder(TreeNode * a){
    if(a == NULL) return;
    postOrder(a->left);
    postOrder(a->right);
    printf("%c",a->data);
}

char Pre[30];
char Med[30];
int main() {
    while(scanf("%s%s",Pre,Med)!=EOF){
        TreeNode * root = rebuild(Pre,Med);
        postOrder(root);
        printf("\n");

    }}
// 64 位输出请用 printf("%lld")