欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PAT 1004 Counting Leaves

程序员文章站 2022-06-11 15:10:39
...

题目描述

英文

PAT 1004 Counting Leaves

中文大意

通过输入的树找出 每一层有多少个叶子节点

样例输出

PAT 1004 Counting Leaves

思路分析

dfs 深度优先遍历, 大致思路是寻找叶子节点, 如果找到在 record[] 数组对应的深度depth 加一

理解一下各个输入

  • N: 节点个数
  • M: 非叶子节点个数
  • ID: 非叶子节点标识
  • K: 此节点的儿子节点数
  • ID[i]: 此节点的儿子节点

首先接受 N、M, 叶子节点不用统计,所以根据M 获取节点

把每个节点的子节点都存入 vector[index]

通过判断vector[index].size() 是否为 0 来判断是否为叶子节点

由于我本人对于 vector 的使用不是很熟悉, 导致 这个vector[]的用法还是参考的别人代码

vector 不是一个动态数组吗?为什么可以通过 vector[index].size() 使用, 此用法有些类似 有序哈希表

code

#include <iostream>
#include <vector>
using namespace std;

vector<int> v[100];
int record[100];

// 深度优先遍历
void dfs(int index, int depth) {
    // 遇到叶节点
    if(v[index].size() == 0) {
        record[depth]++;
        return;
    }
    // 递归
    for(int i = 0;i < v[index].size();i++) {
        dfs(v[index].at(i), depth+1);
    }
}

int main() {
    int N, M, index, K, node, cnt = 0;
    cin >> N >> M;
    for(int i = 0;i < M;i++) {
        cin >> index >> K;
        for(int j = 0;j < K;j++) {
            cin >> node;
            v[index].push_back(node);
        }
    }
    dfs(1, 1);
    // cnt 用于记数 N -M 是叶子节点的总数
    for(int i = 1;cnt != N-M;i++) {
        if (i == 1) cout << record[i];
        else cout << " " << record[i];
        // cnt 记录
        cnt += record[i];
    }
    return 0;
}

题目链接

1004 Counting Leaves (30分)

参考文章

Counting Leaves (30)-PAT甲级真题(bfs,dfs,树的遍历,层序遍历)

C++ STL之vector用法总结