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

Link

Solution

用DFS計算每個子樹的內的字符出現次數

就可以得知ans[]的內容

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

        return cnt;
    }