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;
}