LeetCode高频题：一棵树的第i个节点的权重ai定义为：从根节到该节点的路径上，红色节点和蓝色节点的数量之差，求所有节点的权值之和

提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题

基础知识：

【1】图数据结构，图的统一数据结构和非标准图的转化算法
【2】图的宽度优先遍历：BFS遍历
【3】图的深度优先遍历：DFS遍历

---

文章目录

• LeetCode高频题：一棵树的第i个节点的权重ai定义为：从根节到该节点的路径上，红色节点和蓝色节点的数量之差，求所有节点的权值之和
• • @[TOC](文章目录)
• 题目
• 一、审题
• 理解示例，往往对解题有很大的帮助
• 先bfs求权重，再dfs求权重累加和试试
• 然后利用bfs广播求这个图graph的每个节点的权值
• 然后有了完整的graph，也就是权重ai都有了，就挨个dfs遍历，把ai加入结果ans，返回就是结果了
• okay，本题主函数，只需要先调用bfs算节点们的权重，然后用dfs走一圈，把结果累加就行
• 笔试快速ac代码：其实完全还可以直接一遍bfs就搞定，直接求权值，然后把累加和加到结果上
• 总结

题目

你拿到了一颗有根树，根节点编号为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<>();//邻居没有空
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

每个节点Node内部有自己的id，颜色，权重初始化为0，还有自己的直接邻居nexts，用列表挂好

然后就可以建一个无边的图了

        //图
        public static class Graph{
            public HashMap<Integer, Node> nodes;//图的点集合

            public Graph(){
                nodes = new HashMap();//用哈希表表示我的节点
            }
        }
1
2
3
4
5
6
7
8

实际上这个图，内部放的是一堆节点集合，
题目输入的每一行，就是连节点，相邻有链接的，把两者相互做直接邻居就行
当然了，为了寻找方便，我们用哈希表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);//互加邻居
            }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

就是跟题目说的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);
                    }
                }
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

然后有了完整的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;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

其实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);

        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

测试：结果

5
RBRBB
2 5
1 5
4 1
3 5
3
1
2
3
4
5
6
7

这样就完成了

---

笔试快速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;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

测试结果：

5
RBRBB
2 5
1 5
4 1
3 5
3
1
2
3
4
5
6
7

很OK

笔试你就调用这个函数就搞定了，非常容易

---

总结

提示：重要经验：

0）图的难点在于图的数据结构表示，搞成你熟悉的方法就行，另外，图的算法是不难的，无非就是bfs和dfs运用而已
1）BFS特点用队列搞定，弹出打印，结算结果。
2）DFS是用栈实现的，最重要的2点，压入时结算，弹出不结算，还有就是看cur的邻居之前，必须先把cur再次压栈，保证一条道走到黑，回来还能找到我cur，只压cur的一个邻居，立马break；
3）当然了，一遍bfs搞定也行的，最关键的还是图数据结构的构建
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。