tree.cc

#include <bits/stdc++.h>

void get_post_order(const std::string &pre_order, const std::string &in_order) {
        if (pre_order.length() == 0 && in_order.length() == 0) {
                return;
        } else if (pre_order.length() == 1 && in_order.length() == 0) {
                std::cout << pre_order[0] << ' ';
        } else if (pre_order.length() == 0 && in_order.length() == 1) {
                std::cout << in_order[0] << ' ';
        } else if (pre_order.length() == 1 && in_order.length() == 1) {
                std::cout << pre_order[0] << ' ';
        } else {
                size_t i;
                char ch = pre_order[0];

                for (i = 0; i < in_order.length(); i++) {
                        if (ch == in_order[i])
                                break;
                }

                get_post_order(pre_order.substr(1, i), in_order.substr(0, i));
                get_post_order(pre_order.substr(i+1, -1), in_order.substr(i+1, -1));
                std::cout << ch << ' ';
        }
}

// DGEBHFCA
int main(int argc, char *argv[]) {
        std::string pre_order("ABDEGCFH");
        std::string in_order("DBGEACHF");

        get_post_order(pre_order, in_order);
        std::cout << std::endl;
        return 0;
}