PAT 解题报告 1004. Counting Leaves (30)

题目描述:

统计一颗树每一层的leaf数量。

算法分析:

本质就是lever order traversal, 可以用bfs遍历,然后每一层统计叶子数。

注意点:

这个题目是bfs的变形,可以使用两个queue轮换存储每一层的nodes, 每次bfs的时候都是把其中一个queue清空,把quque里面的所有node的孩子都push到另一个quque中,那么另一个queue中就是下一层的所有node, push的时候顺便统计当前层的叶子数量即可。

Written on January 18, 2013