Hugh

门泊东吴万里船

0%

PAT-1004 Counting Leaves

Posted on Edited on In

思路

就是求解树结构的每一层的叶子节点的树木，使用宽度搜索

源码

line_number: true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <iostream>
#include <stdio.h>
#include <map>
#include <vector>
#include <queue>
using namespace std;
map<string,int> mapNodeLevel; //记录节点所在层数
int iMaxLevel = 0; //记录最大层数
int szNoLeafNode[100]; //记录每层没有孩子的节点数
int main()
{
    int N = 0, M;
    cin>> N >> M;
    map<string, vector<string> > mapTree;
    for(int i = 0; i < M; i++)
    {
        string strRoot;
        cin>> strRoot;
        int iK;
        cin >> iK;
        vector<string> vecChild;
        for(int j = 0; j < iK; j++)
        {
            string strChild;
            cin>> strChild;
            vecChild.push_back(strChild);
        }
        mapTree[strRoot] = vecChild;
    }
    queue<string> queNode;
    queNode.push("01");
    mapNodeLevel["01"] = 0;
    while(queNode.empty() != true)
    {
        string strFrontNode = queNode.front();
        queNode.pop();
        if(mapTree[strFrontNode].size() == 0)
        {
            szNoLeafNode[mapNodeLevel[strFrontNode]] ++;
        }
        iMaxLevel = max(iMaxLevel, mapNodeLevel[strFrontNode]);
        for(int i = 0; i < mapTree[strFrontNode].size(); i++)
        {
            mapNodeLevel[mapTree[strFrontNode][i]] = mapNodeLevel[strFrontNode] + 1;
            queNode.push(mapTree[strFrontNode][i]);
        }
    }
    printf("%d", szNoLeafNode[0]);
    for(int i = 1; i <= iMaxLevel; i++)
    {
        printf(" %d", szNoLeafNode[i]);
    }
    printf("\n");
    return 0;
}