D - The Falling Leaves UVA - 699

╰半橙微兮° 2022-03-22 06:20 170阅读 0赞

### 题目描述： ###

Each year, fall in the North Central region is accompanied by the brilliant colors of the leaves on the  
trees, followed quickly by the falling leaves accumulating under the trees. If the same thing happened  
to binary trees, how large would the piles of leaves become?  
We assume each node in a binary tree ”drops” a number of leaves equal to the integer value stored  
in that node. We also assume that these leaves drop vertically to the ground (thankfully, there’s no  
wind to blow them around). Finally, we assume that the nodes are positioned horizontally in such a  
manner that the left and right children of a node are exactly one unit to the left and one unit to the  
right, respectively, of their parent. Consider the following tree on the right:  
The nodes containing 5 and 6 have the same horizontal po-  
sition (with different vertical positions, of course). The node  
containing 7 is one unit to the left of those containing 5 and  
6, and the node containing 3 is one unit to their right. When  
the ”leaves” drop from these nodes, three piles are created:  
the leftmost one contains 7 leaves (from the leftmost node),  
the next contains 11 (from the nodes containing 5 and 6), and  
the rightmost pile contains 3. (While it is true that only leaf  
nodes in a tree would logically have leaves, we ignore that in  
this problem.)  
Input  
The input contains multiple test cases, each describing a single tree. A tree is specified by giving the  
value in the root node, followed by the description of the left subtree, and then the description of the  
right subtree. If a subtree is empty, the value ‘-1’ is supplied. Thus the tree shown above is specified  
as ‘5 7 -1 6 -1 -1 3 -1 -1’. Each actual tree node contains a positive, non-zero value. The last test  
case is followed by a single ‘-1’ (which would otherwise represent an empty tree).  
Output  
For each test case, display the case number (they are numbered sequentially, starting with 1) on a line  
by itself. On the next line display the number of “leaves” in each pile, from left to right, with a single  
space separating each value. This display must start in column 1, and will not exceed the width of an  
80-character line. Follow the output for each case by a blank line. This format is illustrated in the  
examples below.  
Sample Input  
5 7 -1 6 -1 -1 3 -1 -1  
8 2 9 -1 -1 6 5 -1 -1 12 -1  
\-1 3 7 -1 -1 -1  
\-1  
Sample Output  
Case 1:  
7 11 3  
Case 2:  
9 7 21 15

##### 题意：让我们从左到右输出树叶下落的数量 #####

参考博客：[https://blog.csdn.net/xxx823952375/article/details/26155209][https_blog.csdn.net_xxx823952375_article_details_26155209]

###### 分析： ######

本题，一开始一直在思考建树后如何控制他们的下落。这个定向思维使我久久未能找到出路。  
通过参考博客发现，题目给定了我们一个前序遍历的结果（-1可代表为NULL）。  
那么第一个值一定是根结点，第二个值一定是左子树的根结点。第三个值一定是左子树的左子树（此三个值不为-1）。如果碰到-1，则代表此结点没有左子树。如果下一个值又是-1， 则代表此结点没有右子树。从而依次往回推。分析至此，我们发现，这个可以用递归来书写。

#include"stdio.h"
    #include"string.h"
    int a[80],left,right;
    void dfs(int n,int mid)
    {
    //如果是-1， 直接return
        if(n==-1)
            return ;
        //此两个if是不断更新left和right，是为了输出结果的时候知道范围。
        if(mid<left)
           left=mid;
        if(mid>right)
            right=mid;
        
        a[mid]+=n;
        
        scanf("%d",&n);
        dfs(n,mid-1);//左子树递归
        scanf("%d",&n);
        dfs(n,mid+1);//右子树递归
    
    }
    int main()
    {
        int i,n,count=1;
        while(scanf("%d",&n)&&n!=-1)
        {
            for(i=0;i<80;i++)
                a[i]=0;
            left=40;right=40;
            dfs(n,40);
            printf("Case %d:\n",count++);
            for(i=left;i<right;i++)
                printf("%d ",a[i]);
            printf("%d\n",a[i]);
            printf("\n");
        }
    }

推荐看一下，我参考的博客，里面有图片，更容易理解题意。且写的也比我好。

[https_blog.csdn.net_xxx823952375_article_details_26155209]: https://blog.csdn.net/xxx823952375/article/details/26155209