关于算法-数据结构:PAT甲级1004-Counting-Leaves

题目粗心：

给定一颗树, 要求求出每一层叶子结点的数目

算法思路：

间接遍历这颗树，在遇到叶子节点的时候，就统计以后档次下的叶子节点的个数，这里应用 num_leaves_per_level 保留每一层叶子节点的数目。遍历完结后，间接输入 num_leaves_per_level 数组即可。层序遍历代码如下：

int num_leaves_per_level[101];// 每一层叶子节点的数目
int layer = -1;// 层数

void levelTraverse(int root){
    queue<int> q;
    node[root].level = 1;
    q.push(root);
    while (!q.empty()){int t = q.front();
        q.pop();
        if(layer<node[t].level){layer = node[t].level;
        }
        if(node[t].child.empty()){
            // 叶子节点
            ++num_leaves_per_level[node[t].level];
        } else {// 这里得进行判断，不然会死循环
            for(auto &item:node[t].child){node[item].level = node[t].level+1;
                q.push(item);
            }
        }
    }
}

留神点：

• 层序遍历的时候每次入队都是之前出队的节点。否则会有测试点内存超限和超时。

提交后果：

AC 代码：

#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

struct Node{
    vector<int> child;
    int level;
}node[101];

int num_leaves_per_level[101];// 每一层叶子节点的数目
int layer = -1;// 层数

void levelTraverse(int root){
    queue<int> q;
    node[root].level = 1;
    q.push(root);
    while (!q.empty()){int t = q.front();
        q.pop();
        if(layer<node[t].level){layer = node[t].level;
        }
        if(node[t].child.empty()){
            // 叶子节点
            ++num_leaves_per_level[node[t].level];
        } else {// 这里得进行判断，不然会死循环
            for(auto &item:node[t].child){node[item].level = node[t].level+1;
                q.push(item);
            }
        }
    }
}

int main()
{
    int N,M;// 节点总数和非叶节点个数
    scanf("%d %d",&N,&M);
    if(N==0) return 0;
    int ID,K;
    for (int i = 0; i < M; ++i) {scanf("%d %d",&ID,&K);
        if(K!=0){
            // 非叶子节点
            for (int j = 0; j < K; ++j) {
                int child;
                scanf("%d",&child);
                node[ID].child.push_back(child);
            }
        }
    }
    levelTraverse(1);
    for (int k = 1; k <= layer; ++k) {printf("%d",num_leaves_per_level[k]);
        if(k<layer) printf(" ");
    }
    return 0;
}