欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2023-12-27 08:20:15
...

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
leetcode周赛5465. 子树中标签相同的节点数
输入: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

相关标签: leetcode

上一篇:

下一篇: