uva 699 - The Falling Leaves - dblank

uva 699 - The Falling Leaves

传送门:699 - The Falling Leaves

题意:给你一个树上的节点的序列,这个序列是前序遍历的顺序,然后没有子节点那就是-1,问你这棵树上的在同一水平位置的点的和全部找出,在同一水平是对于根节点的位置,比如根节点的左儿子的右儿子就是和根节点同一水平。

思路:先利用递归把树建好,边建树边统计,进入左子树减1进入右子树加1,这就他的水平位置。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 100000 + 10, Mod = 1000000009;
typedef long long ll;
int ok;
struct treenode
{
    treenode *left;
    treenode *right;
    int data;
};
int lev[N];
treenode *root = new treenode;
treenode* dfs(int lv)
{
    if(ok == 0)
    {
        ok = 1;
        root->left = dfs(lv-1);
        root->right = dfs(lv+1);
    }
    else
    {
        treenode *p = new treenode;
        int x;
        scanf("%d", &x);
      //  cout<<x<<endl;
        if(x == -1)
            return NULL;
        p->data = x;
        lev[50000 + lv] += x;
    //    cout<<p->data<<endl;
        p->left = dfs(lv-1);
        p->right = dfs(lv+1);
    }
}
int main()
{
    int f,cas = 1;
    while(~scanf("%d", &f) && f!=-1)
    {
        ok  = 0;
        memset(lev, 0, sizeof(lev));
        dfs(0);
        root->data = f;
        int sb = 0;
        printf("Case %d:n", cas++);
        lev[50000] += f;
        for(int i = 0; i<N; i++)
        {
            if(lev[i])
            {
                if(sb)
                    printf(" %d", lev[i]);
                else printf("%d", lev[i]), sb++;
            }
        }
        printf("nn");
    }
    return 0;
}

 

相关文章

发表新评论