题解 | #二叉树遍历#

先根据前序遍历和中序遍历结果递归建树，再后续遍历

#include <iostream>
#include <string>

using namespace std;

struct TreeNode {
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char c) : data(c), left(NULL), right(NULL) {}
};

TreeNode* creatBinaryTree(string pStr, string iStr) {
    if (pStr == "" && iStr == "") {
        return NULL;
    }
    char c = pStr[0];
    int pos = iStr.find(c);
    TreeNode* root = new TreeNode(c);
    root->left = creatBinaryTree(pStr.substr(1, pos), iStr.substr(0, pos));
    root->right = creatBinaryTree(pStr.substr(pos+1), iStr.substr(pos+1));
    return root;
}

void lastInorder(TreeNode * root) {
    if (root == NULL) return;
    lastInorder(root->left);
    lastInorder(root->right);
    cout << root->data;
}

int main() 
{
    string pStr;
    string iStr;
    while (cin >> pStr >> iStr) {
        TreeNode* root = creatBinaryTree(pStr, iStr);
        lastInorder(root);
        cout << endl;
    }
    return 0;
}