LeetCode 1519. Number of Nodes in the Sub-Tree With the Same Label

given a tree, containing n nodes and n-1 edges. the root is node 0 and each node has a label(character), that means The node with the number i has the label labels[i].
The edges array is given on the form edges[i] = [ai, bi], which means there is an edge between nodes ai and bi in the tree. (ai bi are both numbers)
Return an array of size n where ans[i] is the number of nodes in the subtree of the ith node which have the same label as node i.

example:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = “abaedcd”
Output: [2,1,1,1,1,1,1]

idea:
这道题目就是很别扭，最后让我们输出一个数组
ans[i]代表第i号node的子树种有多少个标签和这个Node的标签是一样的（当前节点也算是他的子树节点）
输出这样一个数组就行。

简单来说毫无头绪。并且以为这是个很复杂的题目。实际上看看下面的其他人的代码吧，简洁高效。

class Solution {
    public int[] countSubTrees(int n, int[][] edges, String labels) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int[] edge: edges) {
            map.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
            map.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);
        }
        int[] ans = new int[n];
        dfs(map, 0, -1, labels, ans); //dfs contains: map, labels, ans, current node and its parent
        return ans;
    }
    
    private int[] dfs(HashMap<Integer, List<Integer>> map, int node, int parent, String labels, int[] ans) { //return the ans based on curNode and parent
        int[] cnt = new int[26]; //we need to maintain a new
        char c = labels.charAt(node);
        for (int child: map.get(node)) {
            if (child != parent) {  //since it is a tree, we don't need visit array/hashmap to check if we visited it before.
                int[] sub = dfs(map, child, node, labels, ans);
                for (int i = 0; i < 26; i++) {
                    cnt[i] += sub[i];
                }
            }
        }
        cnt[c - 'a']++; //add current node as one
        ans[node] = cnt[c - 'a']; //update ans
        return cnt; //return cnt instead of ans
    }
}

下面的代码是一般的带着visit的实现：

    public int[] countSubTrees(int n, int[][] edges, String labels) {
        Map<Integer, List<Integer>> g = new HashMap<>();
        for (int[] e : edges) {
            g.computeIfAbsent(e[0], l -> new ArrayList<>()).add(e[1]);
            g.computeIfAbsent(e[1], l -> new ArrayList<>()).add(e[0]);
        }
        int[] ans = new int[n];
        Set<Integer> seen = new HashSet<>();
        dfs(g, 0, labels, ans, seen);
        return ans;
    }
    private int[] dfs(Map<Integer, List<Integer>> g, int node, String labels, int[] ans, Set<Integer> seen) {
        int[] cnt = new int[26];
        if (seen.add(node)) {
            char c = labels.charAt(node);
            for (int child : g.getOrDefault(node, Collections.emptyList())) {
                int[] sub = dfs(g, child, labels, ans, seen);
                for (int i = 0; i < 26; ++i) {
                    cnt[i] += sub[i];
                }
            }
            ++cnt[c - 'a'];
            ans[node] = cnt[c - 'a'];
        }
        return cnt;
    }