leetcode周赛5465. 子树中标签相同的节点数

八月 13, 2020

leetcode周赛5465. 子树中标签相同的节点数

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

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

返回一个大小为 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（即，该节点本身）。

注意不一定是二叉树。

自底向上递归的方法

当前节点需要知道下面都有哪些节点，然后把所有的子结点有几个返回（map形式）。虽然看着时间复杂度比较大，但是由于只有小写字母，每次不会消耗太多时间。
具体看代码：

class Solution {
    //自底向上递归，当前节点需要知道下面都有哪些节点，然后把所有的子结点有几个返回（map形式）
    public int[] countSubTrees(int n, int[][] edges, String labels) {
        HashMap<Integer,List<Integer>> map = new HashMap<>(labels.length());
        //build graph
        for (int i = 0; i < edges.length; i++) {
            //无向图存两次边
            List<Integer> tl = map.getOrDefault(edges[i][0], new ArrayList<Integer>());
            tl.add(edges[i][1]);
            map.put(edges[i][0],tl);
            tl = map.getOrDefault(edges[i][1], new ArrayList<>());
            tl.add(edges[i][0]);
            map.put(edges[i][1],tl);
        }
        //System.out.println(map);
        ans = new int[n];
        visited = new int[n];
        HashMap<Character,Integer> tmap = traverse(0,map,labels);
        //System.out.println(tmap);
        return ans;
    }
    private int[] ans;
    private int[] visited;
    private HashMap<Character,Integer> traverse(int root,HashMap<Integer,List<Integer>> map,String lables) {
        HashMap<Character,Integer> res = new HashMap<>();
        if (visited[root] == 1) {//访问过了就不再访问
            return res;
        }
        visited[root] = 1;
        List<Integer> children = map.get(root);
        char r = lables.charAt(root);
        for (Integer i : children) {
            
            if (visited[i] == 1) {
                continue;
            }
            //把子树的节点情况复制过来
            HashMap<Character,Integer> hsc = traverse(i,map,lables);

            //copy
            Iterator<Map.Entry<Character,Integer>> it = hsc.entrySet().iterator();
            while (it.hasNext()) {
                Map.Entry<Character,Integer> en = it.next();
                int t = en.getValue();
                t += res.getOrDefault(en.getKey(),0);
                res.put(en.getKey(),t);
            }
        }
        //加上自己的节点
        int self = res.getOrDefault(r,0) + 1;
        ans[root] = self;
        res.put(r,self);
        
        return res;
    }
}

~~这周做两道就700多名了，微软题还是厉害啊。~~
leetcode 118

查看评论