Data Structures and Algorithms7-21——Counting Leaves

我的Data Structures and Algorithms代码仓：https://github.com/617076674/Data-Structures-and-Algorithms

原题链接：https://pintia.cn/problem-sets/16/problems/683

题目描述：

知识点：树的静态表示法、树的层序遍历

思路：层序遍历树，记录每一层的叶子节点数量

本题和PAT-ADVANCED1004——Counting Leaves的解法一模一样，只不过PAT-ADVANCED1004——Counting Leaves中一个输入文件只包含一个测试用例，而本题中一个输入文件包含多个测试用例。

每个测试用例的时间复杂度和空间复杂度都是O(N)。

C++代码：

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

struct node {
	vector<int> children;
};

int N, M, ID, K, child;

void bfs(node* Node, vector<int> &levelLeaves);

int main() {
	while(true) {
		scanf("%d %d", &N, &M);
		if(N == 0) {
			break;
		}
		node Node[N + 1];
		for(int i = 0; i < M; i++) {
			scanf("%d %d", &ID, &K);
			for(int j = 0; j < K; j++) {
				scanf("%d", &child);
				Node[ID].children.push_back(child);
			}
		}
		vector<int> levelLeaves;
		bfs(Node, levelLeaves);
		for(int i = 0; i < levelLeaves.size(); i++){
			printf("%d", levelLeaves[i]);
			if(i != levelLeaves.size() - 1){
				printf(" ");
			}else{
				printf("\n");
			}
		}
	}
	return 0;
}

void bfs(node* Node, vector<int> &levelLeaves) {
	queue<int> q;
	q.push(1);
	while(!q.empty()) {
		int qSize = q.size();
		int count = 0;
		for(int i = 0; i < qSize; i++) {
			int u = q.front();
			q.pop();
			if(Node[u].children.size() == 0){
				count++;
			}
			for(int j = 0; j < Node[u].children.size(); j++){
				q.push(Node[u].children[j]);
			}
		}
		levelLeaves.push_back(count);
	}
}

C++解题报告：