PAT 甲级 1004 Counting Leaves (30 分) 遍历树求解

ゝ一世哀愁。 2023-08-17 16:27 128阅读 0赞

### 1.题目翻译 ###

#### 输入： ####

每个输入文件包含一个测试用例。每种情况都从包含0 <N <100（树中的节点数）和M（<N）（非叶节点数）的行开始。然后是M行，每行的格式为：

ID K ID[1] ID[2] ... ID[K]

其中ID是代表给定非叶节点的两位数字，K是其子代的数目，后跟其子代的两位ID序列。为了简单起见，让我们将根ID固定为01。

#### 输出 ####

对于每个测试用例，应该从根源开始计算每个资历级别中没有孩子的家庭成员。数字必须成行打印，并用空格隔开，并且每行末尾不得有多余的空格。  
该示例案例表示一棵只有2个节点的树，其中01是根，而02是其唯一的子节点。因此，在根01级别上，存在0个叶节点；在下一个级别上，有1个叶节点。然后，我们应该在一行中输出“ 0 1”。

#### 输入格式 ####

2 1
    01 1 02

#### 输出格式 ####

0 1

### 2.思路分析 ###

1.用一个vector数组存储M个非叶结点的子节点信息，用maxdepth记录树的最大深度，同时用output数组记录每个深度下的叶子结点数  
2.利用深度优先遍历算法（DFS）遍历整颗树  
3.最后输出的时候注意格式，即最后一个数后不能有多余的空格，输出时加个判别语句即可

### 代码 ###

#include<iostream>
    #include<vector>
    using namespace std;
    int max(int a,int b)
    { 
        if(a<b)return b;
        return a;
    }
    vector<int> node[100];//记录每个非叶结点的子结点
    int maxdepth=-1;//记录当前树的最大深度
    int output[100]={ 0};//记录对应深度的叶节点数
    void DFS(int cur_node,int cur_depth)//深度优先遍历树
    { 
        if(node[cur_node].size()==0)
        { 
            output[cur_depth]++;
            maxdepth=max(maxdepth,cur_depth);
            return;
        }
        for(int i=0;i<node[cur_node].size();i++)
        { 
            DFS(node[cur_node][i],cur_depth+1);
        }
    }
    int main()
    { 
        int n,m,id,k,temp;
        cin>>n>>m;
        for(int i=0;i<m;i++)
        { 
            cin>>id>>k;
            for(int j=0;j<k;j++)
            { 
                cin>>temp;
                node[id].push_back(temp);
            }
        }
        DFS(1,0);
        for(int i=0;i<=maxdepth;i++)
        { 
            i==0?cout<<output[i]:cout<<" "<<output[i];
        }
        return 0;
    }