树构造| #Problem D#

根据前序和中序构造二叉树，并使用map优化中序中找根的时间。

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

//树的节点
using Node = struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(char x, TreeNode* left, TreeNode* right) : val(x), left(left),
        right(right) {}
};

map<char, int> ma;
string preOrder, inOrder;

//前序指针，中序指针，子树个数
Node* builderTree(int i, int j, int n) {
    if (n <= 0) return nullptr;
    Node* root = new Node(preOrder[i]);
    int index = ma[preOrder[i]] - j;
    root->left = builderTree(i + 1, j, index);
    root->right = builderTree(i + index + 1, j + index + 1, n - index - 1);
    return root;
}

void afterOrder(Node *root){
    if(root==nullptr) return;
    afterOrder(root->left);
    afterOrder(root->right);
    cout<<root->val;
}


int main() {
    while (cin >> preOrder >> inOrder) { // 注意 while 处理多个 case
        for (int i = 0; i < inOrder.size(); i++)
            ma[inOrder[i]] = i;
        Node *root=builderTree(0, 0, inOrder.size());
        afterOrder(root);
        cout<<endl;
    }
}