UVa 536 Tree Recovery

思路分析：

簡單的根據先序和中序序列重建二叉樹，再後序周遊輸出即可。

題解：

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
struct Node{
	char data;
	Node *left, *right;
};
string str, pre, in;

Node* create(int pl, int pr, int inl, int inr){
	if(pl > pr) return NULL;
	Node* root = new Node;
	root->data = pre[pl];
	int k;
	for(int i = inl; i <= inr; i++){
		if(in[i] == pre[pl]){
			k = i;
			break;
		}
	}
	int leftlen = k - inl;
	root->left = create(pl+1, pl+leftlen, inl, k-1);
	root->right = create(pl+leftlen+1, pr, k+1, inr);
	return root;
}

void postorder(Node* root){
	if(root != NULL){
		postorder(root->left);
		postorder(root->right);
		printf("%c", root->data);
	}
}

int main(){
	while(getline(cin, str) && str != ""){
		int k = -1;
		for(int i = 0; i < str.length(); i++){
			if(str[i] == ' '){
				k = i;
				break;
			}
		}
		pre = str.substr(0, k);
		in = str.substr(k+1, str.length());
		int n = pre.length();
		Node* root = create(0, n-1, 0, n-1);
		postorder(root);
		printf("\n");
	}
	return 0;
}