子树中标签相同的节点数

1519. 子树中标签相同的节点数

给你一棵树（即，一个连通的无环无向图），这棵树由编号从 0 到 n - 1 的 n 个节点组成，且恰好有 n - 1 条 edges 。树的根节点为节点 0 ，树上的每一个节点都有一个标签，也就是字符串 labels 中的一个小写字符（编号为 i 的节点的标签就是 labels[i] ）

边数组 edges 以 edges[i] = [a_i, b_i] 的形式给出，该格式表示节点 a_i 和 b_i 之间存在一条边。

返回一个大小为 n 的数组，其中 ans[i] 表示第 i 个节点的子树中与节点 i 标签相同的节点数。

树 T 中的子树是由 T 中的某个节点及其所有后代节点组成的树。

示例 1：

输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
输出：[2,1,1,1,1,1,1]
解释：节点 0 的标签为 'a' ，以 'a' 为根节点的子树中，节点 2 的标签也是 'a' ，因此答案为 2 。注意树中的每个节点都是这棵子树的一部分。
节点 1 的标签为 'b' ，节点 1 的子树包含节点 1、4 和 5，但是节点 4、5 的标签与节点 1 不同，故而答案为 1（即，该节点本身）。

示例 2：

输入：n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
输出：[4,2,1,1]
解释：节点 2 的子树中只有节点 2 ，所以答案为 1 。
节点 3 的子树中只有节点 3 ，所以答案为 1 。
节点 1 的子树中包含节点 1 和 2 ，标签都是 'b' ，因此答案为 2 。
节点 0 的子树中包含节点 0、1、2 和 3，标签都是 'b'，因此答案为 4 。

示例 3：

输入：n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"
输出：[3,2,1,1,1]

提示：

1 <= n <= 10^5
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
labels.length == n
labels 仅由小写英文字母组成

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) { } };

java 解法, 执行用时: 47 ms, 内存消耗: 106.6 MB, 提交时间: 2023-09-23 11:04:39

class Solution {
    public int[] countSubTrees(int n, int[][] edges, String labels) {
        /*
            后序遍历
        */
        List<Integer>[] points = new List[n];
        for(int i = 0; i < n; i++){
            points[i] = new ArrayList<>();
        }
        for(int[] p : edges){
            points[p[0]].add(p[1]);
            points[p[1]].add(p[0]);
        }

        int[] ls = new int[n];
        for(int i = 0; i < n; i++){
            ls[i] = labels.charAt(i) - 'a';
        }

        res = new int[n];
        visited = new boolean[n];
        visited[0] = true;
        dfs(0, points, ls);
        return res;
    }
    int[] res;
    boolean[] visited;
    private int[] dfs(int i, List<Integer>[] points, int[] ls){
        int[] curLs = new int[26];
        //添加自身节点
        curLs[ls[i]]++;
        for(int child : points[i]){
            /*
                判断是否已经遍历过该节点，如果遍历过，那么跳过
                因为这是无向图, 1 可以到 2，2 也可以到 1，因此，当 1 到 2 的时候，我们需要记录 1 已经访问
                这样，从 2 出发，就不会再到 1 了
            */
            if(visited[child]){
                continue;
            }
            visited[child] = true;
            int[] childLs = dfs(child, points, ls);
            for(int k = 0; k < 26; k++){
                curLs[k] += childLs[k];
            }
        }
        res[i] = curLs[ls[i]];
        return curLs;
    }
}

python3 解法, 执行用时: 1208 ms, 内存消耗: 216.1 MB, 提交时间: 2023-09-23 11:02:26

class Solution:
    def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:
        g = collections.defaultdict(list)
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
        
        def dfs(o: int, pre: int):
            f[o][ord(labels[o]) - ord("a")] = 1
            for nex in g[o]:
                if nex != pre:
                    dfs(nex, o)
                    for i in range(26):
                        f[o][i] += f[nex][i]

        f = [[0] * 26 for _ in range(n)]
        dfs(0, -1)

        ans = [f[i][ord(labels[i]) - ord("a")] for i in range(n)]
        return ans

cpp 解法, 执行用时: 672 ms, 内存消耗: 209.2 MB, 提交时间: 2023-09-23 11:02:01

class Solution {
public:
    vector<vector<int>> g;
    vector<vector<int>> f; 
    
    void dfs(int o, int pre, const string &labels) {
        f[o][labels[o] - 'a'] = 1;
        for (const auto &nex: g[o]) {
            if (nex == pre) {
                continue;
            } 
            dfs(nex, o, labels);
            for (int i = 0; i < 26; ++i) {
                f[o][i] += f[nex][i];
            }
        }
    }
    
    vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
        g.resize(n);
        for (const auto &edge: edges) {
            g[edge[0]].push_back(edge[1]);
            g[edge[1]].push_back(edge[0]);
        }
        f.assign(n, vector<int>(26));
        dfs(0, -1, labels);
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            ans.push_back(f[i][labels[i] - 'a']);
        }
        return ans;
    }
};

golang 解法, 执行用时: 240 ms, 内存消耗: 46.4 MB, 提交时间: 2023-09-23 11:01:37

//1.建立节点间的关系邻接矩阵 
//2.dfs递归计算每个节点子树（包含该节点）每个字母的计数，
// 通过传递父节点排除子节点到父节点的情况代替visited开销 
//3.在递归，归到某个节点是记录下该节点所属字母的计算
func countSubTrees(n int, edges [][]int, labels string) []int {
    relations := genRelations(edges)
    ans := make([]int, n)

    dfs(0, relations, labels,  -1, &ans)
    return ans
}

func dfs(i int, relations [][]int, labels string, visited int, ans *[]int) []int {
    count := make([]int, 26)
    count[labels[i] - 'a']++

    for _, c := range relations[i] {
        if c == visited {
            continue
        }

        re := dfs(c, relations, labels, i, ans)
        for i := 0; i < 26; i++ {
            count[i] += re[i]
        }
    }

    (*ans)[i] = count[labels[i]-'a']
    return count
}

func genRelations(edges [][]int)[][]int {
    relations := make([][]int, len(edges)+1)
    for _, e := range edges {
        relations[e[0]] = append(relations[e[0]], e[1])
        relations[e[1]] = append(relations[e[1]], e[0])
    }

    return relations
}

上一题

下一题

详情