这道题是一个树的层次遍历问题，最常用的方法就是建立队列进行BFS，需要注意的是，
除了根节点固定为01之外，其他结点的顺序可能不固定；序号可能不连续。因此，在组织树时需要建立树编号和结点存储位置的映射。我看很多人用了map或者pair，因为这道题节点数并不多，所以我写了个O（n）复杂度的查找（其实就是遍历找到就退出）。
另外一个技巧是统计逐层的叶节点数量时，如何设置层与层之间的间隔。这里我在BFS时，入队之前每访问一个结点的子结点时，就用父结点层数+1赋给该子结点的层数，然后将子结点入队。当出队时如果出队的结点与队列中的下一个结点层数不同，则说明该层遍历完毕，将统计的数量打印出来。
A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.
Input
Each input file contains one test case. Each case starts with a line containing 0 < N < 100, the number of nodes in a tree, and M (< N), the number of non-leaf nodes. Then M lines follow, each in the format:
ID K ID[1] ID[2] ... ID[K] where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID's of its children. For the sake of simplicity, let us fix the root ID to be 01.
Output
For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.
The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output "0 1" in a line.
Sample Input 2 1 01 1 02 Sample Output 0 1 // 1004. Counting Leaves.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include<vector> #include<queue> #include<iostream> using namespace std; class Node { public: Node(int CNodeID = 0, int CchildNum = 0, int CLevel = -1){ NodeID = CNodeID; childNum = CchildNum; level = CLevel; }; ~Node(){}; vector<Node*> child; int childNum; int NodeID; int level; }; class Tree { public: Tree(int CNodeNum); ~Tree(); vector<Node*> NodeVect; int NodeNum; int findNode(int NodeID); void BFS(); }; Tree::Tree(int CNodeNum) { NodeNum = CNodeNum; } Tree::~Tree() { for (int i = 0; i < NodeVect.size(); i++) delete(NodeVect[i]); vector<Node*>().swap(NodeVect); } int Tree::findNode(int NodeID){ for (int i = 0; i < NodeVect.size(); i++) { if (NodeVect[i]->NodeID == NodeID) return i; } return -1; } void Tree::BFS(){ queue<Node*> q; int rootIndex = findNode(1); if (rootIndex == -1){ cout << 1; return; } NodeVect[rootIndex]->level = 1; int LeafNodeNum = 0; q.push(NodeVect[rootIndex]); while (!q.empty()) { Node frontNode = *q.front(); q.pop(); for (int i = 0; i < frontNode.childNum; i++) { frontNode.child[i]->level = frontNode.level + 1; q.push(frontNode.child[i]); } if (frontNode.childNum == 0) LeafNodeNum++; if (q.empty()){ cout << LeafNodeNum; break; } if (frontNode.level != q.front()->level){ cout << LeafNodeNum << " "; LeafNodeNum = 0; } }//while 循环 } int _tmain(int argc, _TCHAR* argv[]) { int NodeNum, NonLeafNodeNum; cin >> NodeNum >> NonLeafNodeNum; Tree pedigreeTree(NodeNum); while (NonLeafNodeNum--) { int NodeID, K; cin >> NodeID >> K; int NodeIndex = pedigreeTree.findNode(NodeID); if (NodeIndex == -1){ Node* temNode = new Node(NodeID, K); pedigreeTree.NodeVect.push_back(temNode); NodeIndex = pedigreeTree.NodeVect.size() - 1; } else pedigreeTree.NodeVect[NodeIndex]->childNum = K; for (int i = 0; i < K; i++) { int ChildID; cin >> ChildID; int ChildIndex = pedigreeTree.findNode(ChildID); if (ChildIndex == -1){ Node* temNode = new Node(ChildID); pedigreeTree.NodeVect.push_back(temNode); ChildIndex = pedigreeTree.NodeVect.size() - 1; } pedigreeTree.NodeVect[NodeIndex]->child.push_back(pedigreeTree.NodeVect[ChildIndex]); } } pedigreeTree.BFS(); system("pause"); return 0; }