The key of this problem is that we need not build the tree from scratch. In fact, we can direct obtain its post-order traversal results in a recursive manner and the problem has given nice hints on this.
The code is as follows.
1 #include <iostream> 2 #include <string> 3 4 using namespace std; 5 6 string post_order(string pre_order, string in_order) { 7 if (pre_order.empty() && in_order.empty()) 8 return ""; 9 if (pre_order.length() == 1 && in_order.length() == 1) 10 return pre_order; 11 string root = pre_order.substr(0, 1); 12 int rootInOrder = 0; 13 while (in_order[rootInOrder] != pre_order[0]) 14 rootInOrder++; 15 string pl = pre_order.substr(1, rootInOrder); 16 string pr = pre_order.substr(1 + pl.length(), pre_order.length() - pl.length() - 1); 17 string il = in_order.substr(0, rootInOrder); 18 string ir = in_order.substr(rootInOrder + 1, in_order.length() - il.length() - 1); 19 return post_order(pl, il) + post_order(pr, ir) + root; 20 } 21 22 int main(void) { 23 string pre_order, in_order; 24 while (cin >> pre_order >> in_order) 25 cout << post_order(pre_order, in_order); 26 return 0; 27 }
