当前位置: 首页 > news >正文

Leecode刷题C语言之统计好节点的数目

执行结果:通过

执行用时和内存消耗如下:

题目:统计好节点的数目

现有一棵 无向 树,树中包含 n 个节点,按从 0 到 n - 1 标记。树的根节点是节点 0 。给你一个长度为 n - 1 的二维整数数组 edges,其中 edges[i] = [ai, bi] 表示树中节点 ai 与节点 bi 之间存在一条边。

如果一个节点的所有子节点为根的子树包含的节点数相同,则认为该节点是一个 好节点。返回给定树中 好节点 的数量。子树 指的是一个节点以及它所有后代节点构成的一棵树。

解题思路:  

  1. 定义节点结构
    • 使用struct ListNode来表示树中的节点。每个节点包含一个整数值val和一个指向下一个节点的指针next
  2. 创建节点
    • 函数create(int val)用于创建一个新的节点,并初始化其值为val,其next指针为NULL。该函数使用malloc动态分配内存,并检查内存分配是否成功。
  3. 辅助数组和变量
    • subtree_size[100010]:用于存储每个节点的子树大小(包括节点自身)。
    • good_node_cnt:用于计数“好节点”的数量。
  4. 深度优先搜索(DFS)
    • 函数dfs(struct ListNode **adj, int cur, int pa)通过深度优先搜索遍历树。
    • adj是一个数组,其中adj[i]是一个链表的头节点,链表包含所有连接到节点i的节点。
    • cur是当前访问的节点。
    • pa是父节点的索引,用于避免在遍历子节点时回到父节点,形成环路。
    • 在遍历过程中,首先设置当前节点的子树大小为1(只包括节点自身)。
    • 然后遍历当前节点的所有子节点(通过链表),对每个子节点递归调用dfs
    • 累加每个子节点的子树大小到当前节点的子树大小。
    • 跟踪第一个子节点的子树大小,并检查是否所有子节点的子树大小都相等。如果相等,则将当前节点标记为“好节点”。
  5. 构建树的邻接表
    • countGoodNodes函数中,首先计算节点的总数n(等于边数加1,因为无向树有n-1条边)。
    • 初始化邻接表adj,它是一个数组,其中每个元素是一个链表的头节点,链表包含连接到该节点的所有节点。
    • 遍历边数组edges,对于每条边(x, y),创建两个节点(如果尚未存在),并将它们添加到相应的邻接表中,形成双向连接。
  6. 计算好节点的数量
    • 调用dfs函数,从根节点(节点0)开始遍历树。
    • 在遍历完成后,good_node_cnt变量将包含树中“好节点”的总数。
  7. 返回结果
    • 函数countGoodNodes返回“好节点”的总数。
struct ListNode *create(int val) {struct ListNode *node = NULL;node = malloc(sizeof(*node));if (node == NULL) return NULL;node->val = val;node->next = NULL;return node;
}
int subtree_size[100010];
int good_node_cnt;
void dfs(struct ListNode **adj, int cur, int pa) {subtree_size[cur] = 1;int first_child_size = -1;bool is_good_node = true;for (struct ListNode *p = adj[cur]; p != NULL; p = p->next) {int child = p->val;if (child == pa) {continue;}dfs(adj, p->val, cur);subtree_size[cur] += subtree_size[child];if (first_child_size == -1) {first_child_size = subtree_size[child];} else {if (first_child_size != subtree_size[child]) {is_good_node = false;}}}if (is_good_node) {good_node_cnt++;}return ;
}
int countGoodNodes(int** edges, int edgesSize, int* edgesColSize) {int n = edgesSize + 1;good_node_cnt = 0;struct ListNode *adj[n];for (int i = 0; i < n; i++) {adj[i] = NULL;}for (int i = 0; i < edgesSize; i++) {int x = edges[i][0], y = edges[i][1];struct ListNode *xnode = create(x);xnode->next = adj[y];adj[y] = xnode;struct ListNode *ynode = create(y);ynode->next = adj[x];adj[x] = ynode;}dfs(adj, 0, -1);return good_node_cnt;
}

 

http://www.lryc.cn/news/484746.html

相关文章:

  • webpack5 + vue3 从零配置项目
  • Queuing 表(buffer表)的优化实践 | OceanBase 性能优化实践
  • ./mysqld: error while loading shared libraries: libaio.so.1: cannot open sha
  • Qt主线程把数据发给子线程,主线程会阻塞吗
  • 前后端、网关、协议方面补充
  • 如何在Mac上切换到JDK 17开发环境
  • 深入探索 TypeScript:从基础到高级特性
  • Leetcode:118. 杨辉三角——Java数学法求解
  • SHELL脚本(Linux)
  • 单元测试、集成测试、系统测试、验收测试、压力测试、性能测试、安全性测试、兼容性测试、回归测试(超详细的分类介绍及教学)
  • 低代码集成多方API的简单实现
  • 【测试框架篇】单元测试框架pytest(1):环境安装和配置
  • Python数据分析NumPy和pandas(二十九、其他Python可视化工具)
  • Unity中HDRP设置抗锯齿
  • Spring Boot实现文件上传与OSS集成:从基础到应用
  • Python学习26天
  • linux startup.sh shutdown.sh (kkFileView)
  • [MySQL]隐式类型转换
  • 面经总结1
  • Oracle19C AWR报告分析之Instance Efficiency Percentages (Target 100%)
  • 数据结构--数组
  • nrm的安装及使用
  • 【MatLab手记】 --从0到了解超超超详过程!!!
  • 从零创建vue+elementui+sass+three.js项目
  • Linux通过使用scp和sftp发送或拉取文件
  • Jtti:服务器总是自动重启怎么办?
  • 北京大学c++程序设计听课笔记101
  • 一键生成本地SSL证书:打造HTTPS安全环境
  • Unity类银河战士恶魔城学习总结(P124 CharacterStats UI玩家的UI)
  • 速盾:cdn 支持 php 吗?