M02255: 重建二叉树

http://cs101.openjudge.cn/practice/02255/

#include <iostream>

using namespace std;

string preorder, midorder;

void dfs(int lp, int rp, int lm, int rm){
	if (lp > rp) return;
	int rootm = lm;
	while (midorder[rootm] != preorder[lp]) rootm++;
	dfs(lp + 1, lp + rootm - lm, lm, rootm - 1);
	dfs(lp + rootm - lm + 1, rp, rootm + 1, rm);
	cout << preorder[lp];
}

int main(){
	while (cin >> preorder >> midorder){
		int n = preorder.size() - 1;
		dfs(0, n, 0, n);
		cout << endl;
	}
	return 0;
}