PAT (Advanced Level) Practice 1004 Counting Leaves

小灰灰 2023-06-27 06:16 2阅读 0赞

1、不是二叉树，存储方式用到了代码中的结构体。

2、因为结点编号在100以内，可以让第i个结点就存储在tree\[i\]中，方便查找

3、方法：**建树然后层序遍历，遍历时记录layer，和当层无叶子结点的结点个数**

注意：这题题目有个：The input ends with N being 0. That case must NOT be processed.

我以为输入的N为0时，不进行处理，结果加不加判断都能A，所以也不知道给这个说明是来干嘛的，另外，题目本身就说明了N是不可能等于0的。

#include <iostream>
    #include <stdio.h>
    #include <vector>
    #include <queue>
    using namespace std;
    struct Node{
        int data;
        int layer;
        vector<int> child;
    };
    struct Node tree[100];
    int n,m;
    vector<int> result;
    
    void layer(){
        queue<int> q;//tree 的下标
        q.push(1);
        tree[1].layer = 0;
        int layer =0;
        int sum = 0;
        while(!q.empty()){
            int i = q.front();
            q.pop();
            if(tree[i].layer != layer){//层次切换时存储上一层结果
                layer = tree[i].layer;
                result.push_back(sum);
                sum=0;
            }
            if(tree[i].child.size() != 0){
                for(int j=0;j<tree[i].child.size();j++){
                    int h = tree[i].child[j];
                    tree[h].layer = tree[i].layer+1;
                    q.push(h);
                }
            }else{
                sum++;
            }
        }
        //最后的一层
        result.push_back(sum);
    }
    int main()
    {
        scanf("%d",&n);
        if(n == 0) return 0;
        scanf("%d",&m);
        int index,num,c;
        for(int i=0;i<m;i++){
            scanf("%d",&index);
            int num;
            scanf("%d",&num);
            for(int j=0;j<num;j++){
                int ch;
                scanf("%d",&ch);
                tree[index].child.push_back(ch);
            }
        }
        layer();
    
        for(int i=0;i<result.size();i++){
            printf("%d",result[i]);
            if(i!=result.size()-1) printf(" ");
        }
        printf("\n");
        return 0;
    }