LeetCode高频题：一棵树的第i个节点的权重ai定义为：从根节到该节点的路径上，红色节点和蓝色节点的数量之差，求所有节点的权值之和
提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题
基础知识：
【1】图数据结构，图的统一数据结构和非标准图的转化算法
【2】图的宽度优先遍历：BFS遍历
【3】图的深度优先遍历：DFS遍历
文章目录
文章目录
题目
你拿到了一颗有根树，根节点编号为1，每个节点被染成红色或者蓝色
假设第i个节点的权重ai定义为：从根节到该节点的路径上，红色节点和蓝色节点的数量之差，请你算一下，这个树，所有节点的权值之和。
输入描述：
第一行输入一个整数n，代表节点的数量
第二行输入一个长度为n的字符串，R代表第i个节点被染成了红色，B代表第i个节点被染成了蓝色
接下来的n-1行，每行输入两个正整数u v，代表节点u和v有一条路径链接
1<=n<=10的5次方
输出描述：
所有节点的权值之和
一、审题
示例：
输入
5
RBRBB
2 5
1 5
4 1
3 5
输出：
3
理解示例，往往对解题有很大的帮助
根据输入建一个图
不过图是树，没有环
我们来统计每个节点的权值
题目应该说清楚一点，实际上是路径上的R数量-B数量的绝对值
okay，其实我们可以bfs一遍，把每个节点的权值求出来，然后dfs去求累加和
其实完全还可以直接一遍bfs就搞定，直接求权值，然后把累加和加到结果上，看我的文末
注意：这是一家互联网大厂的秋招笔试，题目是真的挺难的，要求你熟悉图的数据结构，图的bfs和dfs
为了给你熟悉图和图的算法，我先将bfs和dfs一起搞的
再给你讲笔试迅速ac的代码【即：其实完全还可以直接一遍bfs就搞定，直接求权值，然后把累加和加到结果上】
先bfs求权重，再dfs求权重累加和试试
这种思路比较清晰
bfs正常从cur=根节点1开始访问，用一个节点Node（内部有编号，颜色，权重）表示
然后不断根据当前节点cur，推cur的邻居的权重，非常简单的
关键就是在建图：
（1）图怎么表示？？——其实一切关于图的算法题，算法是真的不难，就是bfs和dfs，但是图的表示很难
我自己习惯自己的图表示方法，标准图改变来的
这个文章，我讲过标准图的构建方法：
【1】图数据结构，图的统一数据结构和非标准图的转化算法
但是本题，实际上不是图，而是一个树而已
所以，我们也不用建立什么最小生成树，我们只需要统计每个节点的权值，而不需要管边的事情
所以，本题的图节点，完全可以不要边：
//图节点--本题中不需要边
public static class Node{
public int id;
public char color;//染色
public int weight;
public List<Node> nexts;//直接邻居
public Node(int i, char c){
id = i;
color = c;
weight = 0;//初始化权重没有
nexts = new ArrayList<>();//邻居没有空
}
}
每个节点Node内部有自己的id，颜色，权重初始化为0，还有自己的直接邻居nexts，用列表挂好
然后就可以建一个无边的图了
//图
public static class Graph{
public HashMap<Integer, Node> nodes;//图的点集合
public Graph(){
nodes = new HashMap();//用哈希表表示我的节点
}
}
实际上这个图，内部放的是一堆节点集合，
题目输入的每一行，就是连节点，相邻有链接的，把两者相互做直接邻居就行
当然了，为了寻找方便，我们用哈希表nodes存编号id和整个节点，这样既能快速找到根节点1，也能知道这个节点的属性就在Node中
这个建表图的过程，在输入阶段就要搞定
我手撕代码搞定这个过程
Scanner in = new Scanner(System.in);
int N = in.nextInt();//N
String s = in.next();
char[] str = s.toCharArray();//字符串
//计划放入一个邻接表中
Graph graph = new Graph();
for (int i = 0; i < N - 1; i++) {//N-1行
int u = in.nextInt();
int v = in.nextInt();//节点编号//u对应的节点染色
if (!graph.nodes.containsKey(u)) {
graph.nodes.put(u, new Node(u, str[u - 1]));//没有才加这个节点
}
if (!graph.nodes.containsKey(v)) {
graph.nodes.put(v, new Node(v, str[v - 1]));
}
Node from = graph.nodes.get(u);
Node to = graph.nodes.get(v);
from.nexts.add(to);
to.nexts.add(from);//互加邻居
}
就是跟题目说的ACM输入格式一样的东西
只不过每次输入N-1行u v时，我们要把节点，还有直接邻居这些串好就行了
然后利用bfs广播求这个图graph的每个节点的权值
咋做呢？
至于图的bfs咋搞，实在是太简单了，就是跟二叉树的bfs一模一样
你可以看看我写过这个图的bfs代码：
【2】图的宽度优先遍历：BFS遍历
BFS特点用队列搞定，弹出打印，结算结果。
比如刚刚从队列中弹出cur节点，是根节点1，根是红色R，代表权重就是1,
如果是绿色权重认为是-1
看看cur的邻居next们
4和5都一样，颜色是蓝色
故4和5的权重都是
cur.weight + (-1)=1-1=0
懂？
中途访问过的节点，统统放入set中，避免重复遍历
这样一遍就能把所有的节点的权重搞定了
手撕代码：
//有了图，拿着graph，从根节点cur=1出发，bfs广播去求各个节点权重
public static void bfsWriteWeight(Graph graph){
//先找图中的根节点1
Node head = graph.nodes.get(1);
head.weight = head.color == 'R' ? 1 : -1;//红色染1，蓝色染-1
LinkedList<Node> queue = new LinkedList<>();//队列用来做bfs
HashSet<Node> set = new HashSet<>();//访问过的加入set，不要访问了
queue.add(head);
set.add(head);
while (!queue.isEmpty()){
Node cur = queue.poll();//弹出结算
for(Node next : cur.nexts){
//所有邻居，根据cur的weight和next的染色决定next的权重
next.weight = cur.weight + (next.color == 'R' ? 1 : -1);
//然后将其压入队列
if (!set.contains(next)){
queue.add(next);
set.add(next);
}
}
}
}
然后有了完整的graph，也就是权重ai都有了，就挨个dfs遍历，把ai加入结果ans，返回就是结果了
关于图的dfs，我也说过了
【3】图的深度优先遍历：DFS遍历
DFS是用栈实现的，最重要的2点，压入时结算，弹出不结算，还有就是看cur的邻居之前，必须先把cur再次压栈，保证一条道走到黑，回来还能找到我cur，只压cur的一个邻居，立马break；
从cur出发，ans=1
到4，ans+=0，立马break；
返回cur，然后再去看cur的邻居5
到5，ans+=0，立马break；
返回cur，遍历结束，返回ans
这个dfs代码必须熟悉啊
手撕代码：
//graph已经有了权重，那就dfs去取绝对值求和返回
public static int dfsSum(Graph graph){
Node head = graph.nodes.get(1);//根开始遍历吧
Stack<Node> stack = new Stack<>();//用来做dfs的，复习一下
HashSet<Node> set = new HashSet<>();//记录遍历过得
stack.push(head);
set.add(head);
int ans = Math.abs(head.weight);//加入结算
while (!stack.isEmpty()){
Node cur = stack.pop();//弹出不结算，加入时结算
for(Node next : cur.nexts){
if (!set.contains(next)){
//然后重新把cur压栈，里面退出，一条道走到黑，这是dfs绝的重点地方
stack.push(cur);//还必须——先压入cur，这样保证回去还能找到cur
//加邻居
stack.push(next);
ans += Math.abs(next.weight);
set.add(next);
break;
}
}
}
return ans;
}
其实dfs和bfs就是非常简单的关于图的算法了
只要你搞懂了图，怎么表示节点，邻居，还有边（需要考虑边的时候就要把graph中加入边集合哦），剩下的事情都好办了
okay，本题主函数，只需要先调用bfs算节点们的权重，然后用dfs走一圈，把结果累加就行
手撕代码，关键关键的关键
我说了，是图的表达，用你熟悉的图的表达方法，去表示就行
没有什么对错，好坏
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();//N
String s = in.next();
char[] str = s.toCharArray();//字符串
//计划放入一个邻接表中
Graph graph = new Graph();
for (int i = 0; i < N - 1; i++) {//N-1行
int u = in.nextInt();
int v = in.nextInt();//节点编号//u对应的节点染色
if (!graph.nodes.containsKey(u)) {
graph.nodes.put(u, new Node(u, str[u - 1]));//没有才加这个节点
}
if (!graph.nodes.containsKey(v)) {
graph.nodes.put(v, new Node(v, str[v - 1]));
}
Node from = graph.nodes.get(u);
Node to = graph.nodes.get(v);
from.nexts.add(to);
to.nexts.add(from);//互加邻居
}
//有了图，拿着graph，从根节点cur=1出发，bfs广播去求各个节点权重
bfsWriteWeight(graph);
//graph已经有了权重，那就dfs去取绝对值求和返回
int ans = dfsSum(graph);
System.out.println(ans);
}
测试：结果
5
RBRBB
2 5
1 5
4 1
3 5
3
这样就完成了
笔试快速ac代码：其实完全还可以直接一遍bfs就搞定，直接求权值，然后把累加和加到结果上
你上面bfs不是已经彻底搞定了权重吗？？？
本身bfs遍历过所有的节点，而且把他们的权重都求出来了，所以呢，就干呗，中途加入ans即可
手撕代码：
//有了图，拿着graph，从根节点cur=1出发，bfs广播去求各个节点权重——同时直接把它加入ans
public static int bfsWriteWeightSum(Graph graph){
//先找图中的根节点1
Node head = graph.nodes.get(1);
head.weight = head.color == 'R' ? 1 : -1;//红色染1，蓝色染-1
LinkedList<Node> queue = new LinkedList<>();//队列用来做bfs
HashSet<Node> set = new HashSet<>();//访问过的加入set，不要访问了
queue.add(head);
set.add(head);
int ans = 0;
while (!queue.isEmpty()){
Node cur = queue.poll();//弹出结算
ans += Math.abs(cur.weight);//结算结果
for(Node next : cur.nexts){
//所有邻居，根据cur的weight和next的染色决定next的权重
next.weight = cur.weight + (next.color == 'R' ? 1 : -1);
//然后将其压入队列
if (!set.contains(next)){
queue.add(next);
set.add(next);
}
}
}
return ans;
}
测试结果：
5
RBRBB
2 5
1 5
4 1
3 5
3
很OK
笔试你就调用这个函数就搞定了，非常容易
总结
提示：重要经验：
0）图的难点在于图的数据结构表示，搞成你熟悉的方法就行，另外，图的算法是不难的，无非就是bfs和dfs运用而已
1）BFS特点用队列搞定，弹出打印，结算结果。
2）DFS是用栈实现的，最重要的2点，压入时结算，弹出不结算，还有就是看cur的邻居之前，必须先把cur再次压栈，保证一条道走到黑，回来还能找到我cur，只压cur的一个邻居，立马break；
3）当然了，一遍bfs搞定也行的，最关键的还是图数据结构的构建
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。