UVa 548

题意:给中序,后序,然后还原二叉树,再输出从root到leaf节点中节点和最小的那个leaf

很无语的是用index这个变量,居然被判了个CE。。。

#include <stdio.h>
#include 
<string.h>

struct Node
{
    
int l, r, v;
};

char ch;
int inorder[10100], postorder[10100];
Node node[
10100];
int sz, minn, indexn;

void recover(int inl, int inr, int postl, int postr, int &fa)
{
    
if ( inr<inl || postr<postl )
        
return;
    
int p = ++sz;
    fa 
= sz;
    node[p].v
=postorder[postr];
    
int k;
    
for ( k = inl ; k <= inr && inorder[k]!=postorder[postr] ; k++);
    
int len = k-inl;
    recover(inl, k
-1, postl, postl+len-1, node[p].l);
    recover(k
+1, inr, postl+len, postr-1, node[p].r);
}

void dfs(int p, int num)
{
    
if (!node[p].l&&!node[p].r)
    {
        
if ( node[p].v+num < minn )
        {
            indexn 
= node[p].v;
            minn
= node[p].v+num;
        }
        
else if ( node[p].v+num == minn )
            
if ( indexn > node[p].v)
                indexn 
= node[p].v;
        
return;
    }
    node[p].v
+=num;
    
if (node[p].l)
        dfs(node[p].l, node[p].v);
    
if (node[p].r)
        dfs(node[p].r, node[p].v);
}

int main()
{
    
while ( EOF != scanf("%d%c", inorder, &ch) )
    {
        indexn 
= minn = ~1u>>1;
        memset(node, 
0sizeof(node));
        
int top;
        
for ( top = 1 ; ch != '\n' ; top++ )
            scanf(
"%d%c", inorder+top, &ch);
        
for ( int i = 0 ; i < top ; i++ )
            scanf(
"%d", postorder+i);
        recover(
0, top-10, top-1, node[sz=0].r);
        dfs(
10);
        printf(
"%d\n", indexn);
    }
    
return 0;
}

posted on 2012-03-16 17:30 purplest 阅读(428) 评论(0)  编辑 收藏 引用 所属分类: 模拟


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


<2012年3月>
26272829123
45678910
11121314151617
18192021222324
25262728293031
1234567

导航

统计

常用链接

留言簿

随笔分类(70)

随笔档案(68)

ACMer

搜索

最新随笔

最新评论