699 - The Falling Leaves

[cpp] 
描述：這道題內容是通過構造一個二叉樹，看一下那些葉子在樹上時垂直位置是重合的，重合的就加在一塊求和，然後水平輸出就可以了，關鍵是在dfs中的優先遍歷統計葉子在垂直位置的數目和，然後就可以AC了 
 
 
#include <iostream> 
#include <cstdio> 
#include <cstring> 
using namespace std; 
struct Tnode 
{ 
    int c; 
    Tnode *left,*right; 
    Tnode () 
    { 
        c=0; 
        left=right=NULL; 
    } 
}; 
int count; 
Tnode *creat_tree(int l,int *s)//建樹 
{ 
    Tnode *root=new Tnode; 
    if(count<l) 
    { 
        if(s[count]!=-1) 
        { 
            root->c=s[count]; 
            count++; 
            root->left=creat_tree(l,s); 
            count++; 
            root->right=creat_tree(l,s); 
        } 
    } 
    return root; 
} 
void dfs(Tnode *tree,int *s,int l)  //dfs統計，采用寬度優先遍歷 
{ 
    if(tree) 
    { 
        s[l]+=tree->c; 
        dfs(tree->left,s,l-1); 
        dfs(tree->right,s,l+1); 
    } 
} 
int main() 
{ 
    //freopen("a.txt","r",stdin); 
    int n,i,j,flag; 
    int str[100010]; 
    i=j=flag=0; 
    memset(str,0,sizeof(str)); 
    while(scanf("%d",&n)!=EOF) 
    { 
 
        if(n==-1&&j==0&&i==0)break; 
        else str[i+j]=n; 
        if(n==-1) 
        { 
            j++; 
            if(i+1==j) 
            { 
                flag++; 
                printf("Case %d:\n",flag); 
                count=0; 
                i=i+j+1; 
                Tnode *root=creat_tree(i,str); 
                memset(str,0,sizeof(str)); 
                dfs(root,str,1000); 
                for(i=0;; i++)if(str[i]!=0)break; 
                printf("%d",str[i]); 
                for(i=i+1;; i++) 
                    if(str[i]!=0)printf(" %d",str[i]); 
                    else break; 
                printf("\n\n"); 
                memset(str,0,sizeof(str)); 
                i=j=0; 
            } 
        } 
        else i++; 
    } 
    return 0; 
}