예제 6-8 트리 UVa548

1. 제목 설명: 링크 열기 클릭
2. 문제 풀이 사고방식: 본고는 두 갈래 나무의 중서적 역류와 후서적 역류를 제시하고 잎을 찾아 뿌리 결점에 도달할 수 있는 권리와 최소를 요구한다. 만약에 많이 풀면 잎 자체의 권리는 최대한 작아야 한다.우선, 중차적 반복과 후차적 반복에 따라 두 갈래 나무를 세운다. 이 문제는 수조를 이용하여 좌우 트리의 결점 값을 저장한다. 뿌리가 루트인 왼쪽 트리의 결점은lch[root] 오른쪽 트리의 결점은rch[root]이다.
그렇다면 어떻게 중서에 따라 두루 다니고, 후서에 따라 차례로 나무를 세울 수 있을까?방법은 뒷순서에 따라 뿌리를 찾은 다음에 중순서에서 뿌리를 찾아 좌우 나무의 결점 목록을 찾아서 좌우 나무를 구성하면 된다.마지막으로 먼저 차례대로 가장 좋은 잎사귀 결점을 구해낸다.
3. 코드:

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<functional>
using namespace std;

#define N 10000+10
int in_order[N], post_order[N], lch[N], rch[N];
int n;
bool read_list(int*a)
{
	string line;
	if (!getline(cin, line))
		return false;
	stringstream ss(line);
	n = 0;
	int x;
	while (ss >> x)a[n++] = x;
	return n > 0;
}
int build(int L1, int R1, int L2, int R2)// 
{
	if (L1 > R1)return 0;
	int root = post_order[R2];
	int p = L1;
	while (in_order[p] != root)p++;
	int cnt = p - L1;
	lch[root] = build(L1, p - 1, L2, L2 + cnt - 1);// 
	rch[root] = build(p + 1, R1, L2 + cnt, R2 - 1);// 
	return root;
}
int best, best_sum;
void dfs(int u, int sum)// 
{
	sum += u;
	if (!lch[u] && !rch[u])
	{
		if (sum < best_sum || (sum == best_sum&&u < best))
		{
			best = u;
			best_sum = sum;
		}
	}
	if (lch[u])dfs(lch[u], sum);
	if (rch[u])dfs(rch[u], sum);
}
int main()
{
	//freopen("t.txt", "r", stdin);
	while (read_list(in_order))
	{
		read_list(post_order);
		build(0, n - 1, 0, n - 1);
		best_sum = 100000000;
		dfs(post_order[n - 1], 0);
		cout << best << endl;
	}
	return 0;
}