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
输入: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