随笔-68  评论-10  文章-0  trackbacks-0
题目链接: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 inint post, int sum)
{
    
if(num == 0return;
    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 
- inin, 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 - 10);
        cout 
<< leaf << endl;
    }

    
return 0;
}


posted on 2011-11-25 14:50 wuxu 阅读(331) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理