题解 | 二叉树遍历

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

//两个字符串，其长度n均小于等于26。
//第一行为前序遍历，第二行为中序遍历。 二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。

//输入样例可能有多组，对于每组测试样例， 输出一行，为后序遍历的字符串。

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

TreeNode* RebuildTree(string strP, string strI) {
    if (strP.size() == 0) {
        return NULL;
    }
    char root = strP[0];
    TreeNode* pnew = new TreeNode;
    pnew->data = root;
    int pos = strI.find(root);
    pnew->left = RebuildTree(strP.substr(1, pos), strI.substr(0, pos));
    pnew->right = RebuildTree(strP.substr(pos + 1), strI.substr(pos + 1));
    return pnew;
}

void PostOrder(TreeNode* proot) {
    if (proot == NULL) {
        return;
    }
    PostOrder(proot->left);
    PostOrder(proot->right);
    printf("%c", proot->data);
}

int main() {
    char strP[27];
    char strI[27];
    while (scanf("%s %s", strP, strI) != EOF) {
        TreeNode* proot;
        int n = 0;
        proot = RebuildTree(strP, strI);
        PostOrder(proot);
        printf("\n");
    }
    return 0;
}