PATEST-A1004-题解

START:

我从来不会咕咕咕的。

题目

题意是输出二叉树的每一层叶节点的个数。

解法

bfs + 队列实现层序遍历。

源码

/*
	几乎没有过几个测试点的代码我就敢放上来，
	真的是佩服我的勇气呢!
	未 AC 代码
*/
#include <iostream>
#include <queue>
#include<vector>

using namespace std;

int N;//树的节点数
int M;//树的非叶子节点树

vector<vector<int>> ID;
vector <int> v;
queue<int> q;

int main()
{
	for (int i = 0; i < 100; i++)
	{
		ID.push_back(vector<int>());
	}
	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		int  id, k;
		cin >> id;
		cin >> k;//有几个子节点
		for (int j = 0; j < k; j++)
		{
			int id2;
			cin >> id2;
			ID[id].push_back(id2);

		}//end for j

	}//end for i


	q.push(1);
	while (!q.empty())
	{
		int size = q.size();
		int count;
		for (int i = 0; i < size; i++)
		{
			int top = q.front();
			q.pop();
			if (ID[top].size() == 0)//无孩子，叶子节点
			{
				count++;
			}
			else
			{
				for (int j = 0; j < ID[top].size(); j++)
				{
					q.push(ID[top][j]);
				}
			}
			v.push_back(count);
		}
	}
	cout << v[0];
	for (int i = 1; i < v.size(); i++)
	{
		cout << " " << v[i];
	}

}

吐槽

二维 vector 数组最好固定行，不然每一次用之前都需要往里头传一个一维 vector 数组，不然会越界。

END