1004 Counting Leaves (30分)-白红宇

1004 Counting Leaves (30分)

阅读量：392 次

发布时间：2019-03-05

本文共 1790 字，大约阅读时间需要 5 分钟。

为了解决这个问题，我们需要计算每一层的无子节点数量，包括根节点。我们将使用广度优先搜索（BFS）来逐层遍历树，并统计每一层的无子节点数量。

方法思路

输入处理：读取输入数据，构建树的结构，记录每个节点的子节点。

广度优先搜索（BFS）：从根节点开始，逐层访问每个节点，统计每一层的无子节点数量。

层序遍历：对于每个节点，检查其是否为叶子节点。如果是，则计入当前层的无子节点数量；否则，将其子节点加入队列，继续处理下一层。

解决代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int main() {    int n, m;    scanf("%d %d", &n, &m);    unordered_map

> tree; for (int i = 0; i < m; ++i) { string line; // 读取一整行，去掉可能的换行符 while (getline(line, cin) && line.empty()) continue; // 分割成各个部分 vector

parts; size_t start = 0; size_t end = line.find(' '); while (end != string::npos) { parts.push_back(line.substr(start, end - start)); start = end + 1; end = line.find(' ', start); } parts.push_back(line.substr(start)); // 解析t int t; sscanf(parts[0].c_str(), "%d", &t); int k = stoi(parts[1]); vector

children; for (size_t j = 2; j < parts.size(); ++j) { int child; sscanf(parts[j].c_str(), "%d", &child); children.push_back(child); } tree[t] = children; } // 处理BFS queue

q; q.push(1); // 根节点是01，对应整数1. vector

res; while (!q.empty()) { int level_size = q.size(); int count = 0; for (int i = 0; i < level_size; ++i) { int node = q.front(); q.pop(); bool is_leaf = true; if (tree.find(node) != tree.end()) { if (tree[node].size() == 0) { is_leaf = true; } else { is_leaf = false; } } else { is_leaf = true; } if (is_leaf) { count++; } else { for (int child : tree[node]) { q.push(child); } } } res.push_back(count); } // 输出结果 if (!res.empty()) { for (size_t i = 0; i < res.size(); ++i) { if (i > 0) { cout << " "; } cout << res[i]; } } return 0;}

代码解释

输入处理：读取输入数据，解析每个非叶子节点的信息，构建树的结构。

BFS初始化：从根节点开始，使用队列进行层序遍历。

层序遍历：逐层处理每个节点，判断其是否为叶子节点，统计无子节点数量。

结果输出：将每一层的无子节点数量输出，层与层之间用空格分隔。

通过这种方法，我们能够高效地计算每一层的无子节点数量，并处理所有测试用例。

转载地址：http://jzbwz.baihongyu.com/

你可能感兴趣的文章

poj 3468 A Simple Problem with Integers（线段树插线问线）