PATEST-A1004-题解1

START:

题目

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

解法

dfs。

源码

/*
	只放关键代码
*/

void dfs(int index, int depth)
{
	/*
		当发现叶子节点时，层叶子节点数加一
		并与最大层数比较，让最大层数变化
	*/
	if (v[index].size() == 0)
	{
		book[depth]++;
		maxdepth = max(maxdepth, depth);
		return;
	}
    
	/*
		从根节点开始遍历
	*/
	for (int i = 0; i < v[index].size(); i++)
	{
		dfs(v[index][i], depth + 1);
	}
}

int main()
{
    ...
    //end for i j
    dfs(1, 0);
}

吐槽

我为什么 bfs 的时候要开一个二维 vector ，直接 push_back() 进去数据就好了。

参考

柳婼 の blog 柳大的博客。

END