[TIOJ] 1108. 樹的三兄弟

題目連結:http://tioj.infor.org/problems/1108

---

因為二元搜尋樹有幾個棒棒的性質，那就是依照前序遍歷插入會得到原樹(後序倒著插入也會是好的)，而中序遍歷即為其大小關係，故只要用中序得到如何比大小，用前序插入就可建構出原樹，再自己後序一遍就好XDD，而雖然這題是二元樹，但你還是可以把它當二元搜尋樹搞

#include <bits/stdc++.h>
using namespace std;

int Map[256];

struct node{
	node* l;
	node* r;
	char x;
	node(){l=NULL;r=NULL;}
	node(char a){l=NULL;r=NULL;x=a;}
};
void insert(node*,node*&);
void remove(node*);
void dfs(node*);

int main(){
	char pre[60], in[60];
	while(scanf("%s\n%s",pre,in)!=EOF){
		vector<node*> vv;
		int sz=strlen(in);
		for(int i=0;i<sz;i++)Map[in[i]]=i;
		auto root = new node(pre[0]);
		for(int i=1;i<sz;i++){
			auto tmp = new node(pre[i]);
			insert(tmp,root);
			vv.push_back(tmp);
		}
		dfs(root);putchar('\n');
		remove(root);
	}
	return 0;
}

void insert(node* x,node*& rr){
	if(rr==NULL) rr=x;
	else{
		if(Map[x->x]>Map[rr->x]) insert(x,rr->r);
		else insert(x,rr->l);
	}
}

void remove(node* rr){
	if(rr->l)remove(rr->l);
	if(rr->r)remove(rr->r);
	delete rr;
}

void dfs(node* rr){
	if(rr->l)dfs(rr->l);
	if(rr->r)dfs(rr->r);
	putchar(rr->x);
}