题目链接：
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=489
递归求解，可以不用建树。
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
using namespace std;
const int minn = 100000005;
int inorder[10002];
int postorder[10002];
int leaf, minval;
void proc_tree(int num, int in, int post, int sum)
{
if(num == 0) return;
sum += postorder[post];
if(num == 1)
{
if(sum < minval)
{
minval = sum;
leaf = postorder[post];
}
else if(sum == minval && leaf < postorder[post])
{
leaf = postorder[post];
}
return;
}
int pos = find(inorder + in, inorder + in + num, postorder[post]) - inorder;
proc_tree(num - (pos - in + 1), pos + 1, post -1, sum);
proc_tree(pos - in, in, post - num + pos - in, sum);
}
int main()
{
int n;
string si, sp;
while(getline(cin, si))
{
getline(cin, sp);
n = 0;
stringstream strmi(si);
while(strmi >> inorder[n]) ++n;
n = 0;
stringstream strmp(sp);
while(strmp >> postorder[n]) ++n;
leaf = -1;
minval = minn;
proc_tree(n, 0, n - 1, 0);
cout << leaf << endl;
}
return 0;
}
posted on 2011-11-25 14:50
wuxu 阅读(313)
评论(0) 编辑 收藏 引用 所属分类:
数据结构