USACO 3.4 American Heritage

Probably the most easiest problem solved on USACO so far?

#include <vector>
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

string preorder;
string inorder;
string postorder;

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

TreeNode *construct(int preStart, int preEnd, int inStart, int inEnd) {
    if (preStart > preEnd || inStart > inEnd) return nullptr;
    auto root = new TreeNode(preorder[preStart]);
    int index = 0;
    for (int i = inStart; i <= inEnd; ++i) {
        if (inorder[i] == preorder[preStart]) {
            index = i; break;
        }
    }
    
    root->left = construct(preStart + 1, preStart + index - inStart,
                           inStart, index - 1);
    root->right = construct(preStart + index - inStart + 1, preEnd,
                            index + 1, inEnd);
    return root;
}

void postTraverse(TreeNode *root) {
    if (!root) return;
    postTraverse(root->left);
    postTraverse(root->right);
    postorder += root->c;
}

int main() {
    ifstream fin("heritage.in");
    ofstream fout("heritage.out");
    fin >> inorder >> preorder;
    int size = (int)inorder.size();
    postTraverse(construct(0, size - 1, 0, size - 1));
    cout << postorder << endl;
    fout << postorder << endl;
}