广西南宁网站排名优化,app商城软件,wordpress 国产插件,广州做网站专业公司执行结果:通过
执行用时和内存消耗如下#xff1a; 题目#xff1a;统计好节点的数目
现有一棵 无向 树#xff0c;树中包含 n 个节点#xff0c;按从 0 到 n - 1 标记。树的根节点是节点 0 。给你一个长度为 n - 1 的二维整数数组 edges#xff0c;其中 edges[i] [ai,…执行结果:通过
执行用时和内存消耗如下 题目统计好节点的数目
现有一棵 无向 树树中包含 n 个节点按从 0 到 n - 1 标记。树的根节点是节点 0 。给你一个长度为 n - 1 的二维整数数组 edges其中 edges[i] [ai, bi] 表示树中节点 ai 与节点 bi 之间存在一条边。
如果一个节点的所有子节点为根的子树包含的节点数相同则认为该节点是一个 好节点。返回给定树中 好节点 的数量。子树 指的是一个节点以及它所有后代节点构成的一棵树。
解题思路 定义节点结构 使用struct ListNode来表示树中的节点。每个节点包含一个整数值val和一个指向下一个节点的指针next。创建节点 函数create(int val)用于创建一个新的节点并初始化其值为val其next指针为NULL。该函数使用malloc动态分配内存并检查内存分配是否成功。辅助数组和变量 subtree_size[100010]用于存储每个节点的子树大小包括节点自身。good_node_cnt用于计数“好节点”的数量。深度优先搜索DFS 函数dfs(struct ListNode **adj, int cur, int pa)通过深度优先搜索遍历树。adj是一个数组其中adj[i]是一个链表的头节点链表包含所有连接到节点i的节点。cur是当前访问的节点。pa是父节点的索引用于避免在遍历子节点时回到父节点形成环路。在遍历过程中首先设置当前节点的子树大小为1只包括节点自身。然后遍历当前节点的所有子节点通过链表对每个子节点递归调用dfs。累加每个子节点的子树大小到当前节点的子树大小。跟踪第一个子节点的子树大小并检查是否所有子节点的子树大小都相等。如果相等则将当前节点标记为“好节点”。构建树的邻接表 在countGoodNodes函数中首先计算节点的总数n等于边数加1因为无向树有n-1条边。初始化邻接表adj它是一个数组其中每个元素是一个链表的头节点链表包含连接到该节点的所有节点。遍历边数组edges对于每条边(x, y)创建两个节点如果尚未存在并将它们添加到相应的邻接表中形成双向连接。计算好节点的数量 调用dfs函数从根节点节点0开始遍历树。在遍历完成后good_node_cnt变量将包含树中“好节点”的总数。返回结果 函数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;
}
