2025-03-21：统计好节点的数目。用go语言，给定一棵无向树，树中有 n 个节点，节点的标号从 0 到 n - 1，根节点

福大大架构师每日一题

发布于 2025-03-21 17:20:08

2530

2025-03-21：统计好节点的数目。用go语言，给定一棵无向树，树中有 n 个节点，节点的标号从 0 到 n - 1，根节点为 0。我们有一个长度为 n - 1 的二维数组 edges，其中 edges[i] = [ai, bi] 表示节点 ai 和节点 bi 之间有一条边。

如果一个节点的所有子节点所构成的子树中，包含的节点数都相同，则该节点被称为“好节点”。你的任务是计算出在这棵树中有多少个“好节点”。

2 <= n <= 100000。

edges.length == n - 1。

edges[i].length == 2。

0 <= ai, bi < n。

输入确保 edges 总表示一棵有效的树。

输入：edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]。

输出：7。

解释：

树中的节点都是好节点。

题目来自leetcode3249。

大体步骤如下：

1.首先定义了一个 countGoodNodes 函数，接收一个二维数组 edges，表示树的边的关系。

2.初始化树的节点个数 n 为 len(edges) + 1，创建一个二维数组 g 用来表示节点之间的关系。

3.构建图的邻接表 g，将节点之间的连接关系存储在邻接表中。

4.初始化变量 res 用来统计“好节点”数量。

5.定义一个内部递归函数 dfs，用来遍历节点并统计每个节点的子树大小。

6.在 dfs 函数中，遍历当前节点的子节点，通过递归调用 dfs 函数计算子节点的大小，并判断子节点所构成的子树节点数是否相同。

7.如果子节点构成的子树节点数相同，则将当前节点标记为“好节点”，统计“好节点”的数量。

8.递归遍历整棵树，从根节点开始。

9.在 main 函数中构造示例输入 edges 作为树的边的关系，调用 countGoodNodes 函数计算“好节点”数量，并打印结果。

总的时间复杂度：

• 因为每个节点仅遍历一次，所以遍历整棵树的时间复杂度为 O(n)，其中 n 为节点的数量。
• 在 dfs 函数中，对每个节点的子节点进行遍历，时间复杂度也为 O(n)。
• 因此，总的时间复杂度为 O(n)。

总的额外空间复杂度：

• 使用了邻接表 g 来存储节点之间的关系，占用的额外空间为 O(n)。
• 递归调用时会产生递归栈的空间，最坏情况下会达到 O(n)。
• 因此，总的额外空间复杂度约为 O(n)。

Go完整代码如下：

package main

import (
    "fmt"
)

func countGoodNodes(edges [][]int)int {
    n := len(edges) + 1
    g := make([][]int, n)
    for _, edge := range edges {
        x, y := edge[0], edge[1]
        g[x] = append(g[x], y)
        g[y] = append(g[y], x)
    }
    res := 0
    var dfs func(node, parent int)int
    dfs = func(node, parent int)int {
        valid := true
        treeSize := 0
        subTreeSize := 0

        for _, child := range g[node] {
            if child != parent {
                size := dfs(child, node)
                if subTreeSize == 0 {
                    subTreeSize = size
                } elseif size != subTreeSize {
                    valid = false
                }
                treeSize += size
            }
        }
        if valid {
            res++
        }
        return treeSize + 1
    }

    dfs(0, -1)
    return res
}

func main() {
    edges := [][]int{{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}}
    result := countGoodNodes(edges)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

defcountGoodNodes(edges):
    n = len(edges) + 1
    g = [[] for _ inrange(n)]
    
    for x, y in edges:
        g[x].append(y)
        g[y].append(x)
    
    res = 0

    defdfs(node, parent):
        nonlocal res
        valid = True
        treeSize = 0
        subTreeSize = 0

        for child in g[node]:
            if child != parent:
                size = dfs(child, node)
                if subTreeSize == 0:
                    subTreeSize = size
                elif size != subTreeSize:
                    valid = False
                treeSize += size
        
        if valid:
            res += 1
        
        return treeSize + 1
    
    dfs(0, -1)
    return res


if __name__ == "__main__":
    edges = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]
    result = countGoodNodes(edges)
    print(result)