从这个题目我们再次学习到了一个知识点，就是递归函数的强大！
首先，我们先明确一个知识点，就是你知道了一棵树的中序和后序遍历，求他的前序遍历，我们应该怎么来做？
第一步：最初的时候，我们的后序遍历的最后一个数字就是我们的一个子树的根节点
第二步：找到我们的根结点后，跟据我们中序遍历的性质，我们的树就会被自然地分成了左右两个部分。
第三步：统计出来左右两个子树的大小和长度，这样就能继续重复上面的步骤
这道题的读写输入也是一个知识点，这个我是直接看的刘汝佳的知识点来做的。
总之，递归很强大很强大！
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int maxn = 10000+10;
const int INF = 1e9;
int in_order[maxn], post_order[maxn];
int n;
int lch[maxn], rch[maxn];
int index,maxx;
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_tree(int L1, int R1, int L2, int R2)
{
if(L1 > R1)
return 0;
int p = L1;
int root = post_order[R2];
while(in_order[p] != root)
p++;
int cnt = p - L1;
//本题目的核心其实就是这两步，这两步一定要好好地思考一下，就是递归在建树这里的运用
//怎么去理解我传递的参数？不要去理解成什么长度了，只要理解成数组的起始和终止坐标就好
lch[root] = build_tree(L1, p - 1, L2, L2 + cnt-1);
rch[root] = build_tree(p+1, R1, L2+cnt,R2-1);
return root;
}
void dfs(int root, int sum)
{
sum += root;
if(!lch[root] && !rch[root])
{
if(sum < maxx || (sum == maxx && root < index))
{
maxx = sum;
index = root;
}
}
if(lch[root])
dfs(lch[root], sum);
if(rch[root])
dfs(rch[root], sum);
}
int main()
{
while(read_list(in_order))
{
read_list(post_order);
//int len = n - 1; // 最后一个数字的下标，长度的话就是n
int root = build_tree(0,n-1,0,n-1);
//printf("%d\n", root);
maxx = INF;
index = root;
dfs(root, 0);
printf("%d\n", index);
}
return 0;
}
原文：http://www.cnblogs.com/fzfn5049/p/5951415.html