LeetCode 3373. 连接两棵树后最大目标节点数目 II — Java 实现题目描述有两棵无向树分别有 n 和 m 个节点。给定两棵树的边 edges1 和 edges2。如果节点 u 和节点 v 之间路径的边数是偶数则称 u 是 v 的目标节点。一个节点一定是它自己的目标节点。返回长度为 n 的数组 answeranswer[i] 表示将第一棵树中节点 i 与第二棵树中某个节点连接一条边后第一棵树中节点 i 的目标节点数目的最大值。核心思路黑白染色法树是二分图可以用 0/1 染色来区分节点深度的奇偶性- 相邻节点颜色不同0 和 1 交替- 相同颜色的节点之间距离为偶数目标节点关系- 不同颜色的节点之间距离为奇数所以对每棵树染色后统计颜色 0 和颜色 1 的节点数量即可。对于第一棵树的节点 i- 树1中的目标节点 与 i 同色的节点数- 连接树2后树2中的目标节点 可以选择树2中颜色更多的那一类通过选择连接树2中对应颜色的节点使距离为偶数Java 实现javaimport java.util.ArrayList;import java.util.List;class Solution {public int[] maxTargetNodes(int[][] edges1, int[][] edges2) {int n edges1.length 1;int m edges2.length 1;// 颜色数组0 表示偶数深度1 表示奇数深度int[] colours1 new int[n];int[] colours2 new int[m];// 分别对两棵树染色返回 [颜色0的节点数, 颜色1的节点数]int[] count1 build(edges1, colours1);int[] count2 build(edges2, colours2);// 树2中颜色较多的节点数连接后可以全部作为目标节点int maxFromTree2 Math.max(count2[0], count2[1]);int[] ans new int[n];for (int i 0; i n; i) {// 树1中同色节点数 树2中可贡献的最大节点数ans[i] count1[colours1[i]] maxFromTree2;}return ans;}/*** 构建邻接表并对树进行染色* param edges 树的边* param colours 颜色数组出参* return [颜色0的节点数, 颜色1的节点数]*/private int[] build(int[][] edges, int[] colours) {int n edges.length 1;// 构建邻接表ListListInteger graph new ArrayList();for (int i 0; i n; i) {graph.add(new ArrayList());}for (int[] edge : edges) {graph.get(edge[0]).add(edge[1]);graph.get(edge[1]).add(edge[0]);}// DFS 染色从节点0开始深度为0颜色0int count0 dfs(graph, 0, -1, 0, colours);return new int[] { count0, n - count0 };}/*** DFS 遍历并染色* param graph 邻接表* param u 当前节点* param pre 父节点* param distance 当前深度* param colours 颜色数组* return 颜色0的节点数*/private int dfs(ListListInteger graph, int u, int pre, int distance, int[] colours) {colours[u] distance % 2; // 偶数深度染0奇数深度染1// 统计颜色0的节点数int count (distance % 2 0) ? 1 : 0;for (int v : graph.get(u)) {if (v ! pre) {count dfs(graph, v, u, distance 1, colours);}}return count;}}另一种更简洁的写法使用 BFSjavaimport java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.Queue;class Solution {public int[] maxTargetNodes(int[][] edges1, int[][] edges2) {int n edges1.length 1;int m edges2.length 1;int[] colours1 new int[n];int[] colours2 new int[m];int[] count1 bfsColour(edges1, colours1);int[] count2 bfsColour(edges2, colours2);int maxFromTree2 Math.max(count2[0], count2[1]);int[] ans new int[n];for (int i 0; i n; i) {ans[i] count1[colours1[i]] maxFromTree2;}return ans;}private int[] bfsColour(int[][] edges, int[] colours) {int n edges.length 1;ListInteger[] graph new ArrayList[n];for (int i 0; i n; i) {graph[i] new ArrayList();}for (int[] e : edges) {graph[e[0]].add(e[1]);graph[e[1]].add(e[0]);}int[] count new int[2];Queueint[] queue new ArrayDeque();queue.offer(new int[]{0, 0}); // [节点, 颜色]colours[0] 0;boolean[] visited new boolean[n];visited[0] true;while (!queue.isEmpty()) {int[] curr queue.poll();int u curr[0], color curr[1];count[color];for (int v : graph[u]) {if (!visited[v]) {visited[v] true;colours[v] color ^ 1; // 翻转颜色queue.offer(new int[]{v, colours[v]});}}}return count;}}复杂度分析指标 复杂度时间 O(n m) — 每棵树遍历一次空间 O(n m) — 邻接表 颜色数组关键点说明1. 染色原理树是二分图相邻节点颜色不同。相同颜色节点之间的距离为偶数目标节点不同颜色为奇数。2. 树2的贡献对于树2我们可以自由选择连接哪个节点。如果树2中颜色0的节点更多就将树1的节点连接到树2中颜色1的节点上这样树2中所有颜色0的节点到树1节点的距离都是偶数1奇数偶数。反之亦然。3. 树1的贡献节点 i 的目标节点就是树1中与它同色的所有节点。4. 最终答案answer[i] 树1中同色节点数 max(树2中颜色0数, 树2中颜色1数)验证示例示例 1edges1 [[0,1],[0,2],[2,3],[2,4]], edges2 [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]]- 树1染色节点0(0), 1(1), 2(1), 3(0), 4(0) → 颜色0: 3个(0,3,4), 颜色1: 2个(1,2)- 树2染色颜色0: 4个, 颜色1: 4个 → max 4- answer[0] 3 4 7... 实际输出 [8,7,7,8,8]等等让我重新检查树1有5个节点颜色0: 3个, 颜色1: 2个。树2有8个节点。实际上示例1中树2颜色0和1各有4个max4。但答案中节点0是8说明 3 4 7 不对...重新理解节点到自己的距离是0偶数所以每个节点自己是目标节点。树1中节点0的颜色是0同色节点有 0,3,4 共3个。但答案是8说明树2贡献了5个让我重新分析连接后节点0到树2中某节点v的距离 树1中0到连接点的距离 1 树2中v到连接点的距离。如果树1中节点0连接到树2的节点x那么树2中节点y到0的距离 dist(0, connect) 1 dist(x, y)。要使这个距离为偶数需要 dist(0, connect) 1 dist(x, y) 为偶数。如果0和connect同色dist为偶则需要 1 dist(x,y) 为偶即 dist(x,y) 为奇数y与x异色。如果0和connect异色dist为奇则需要 1 dist(x,y) 为奇即 dist(x,y) 为偶数y与x同色。所以对于树1中颜色为c的节点i- 连接树2中颜色为 (c^1) 的节点则树2中颜色为 c 的节点都是目标节点- 连接树2中颜色为 c 的节点则树2中颜色为 (c^1) 的节点都是目标节点取最大值即可max(count2[0], count2[1])树1中节点0颜色为0同色节点3个。3 4 7 还是不对...哦我数错了。重新看树1edges1 [[0,1],[0,2],[2,3],[2,4]]- 0: 深度0, 颜色0- 1: 深度1, 颜色1- 2: 深度1, 颜色1- 3: 深度2, 颜色0- 4: 深度2, 颜色0颜色0: 0,3,4 → 3个。颜色1: 1,2 → 2个。但答案是8树1有5个节点树2有8个节点。8 5 3或者 8 3 5如果树2颜色0:4, 颜色1:4那max4。347≠8。让我重新检查树2edges2 [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]]8个节点7条边。- 0: 深度0, 颜色0- 1: 深度1, 颜色1- 2: 深度1, 颜色1- 3: 深度1, 颜色1- 4: 深度2, 颜色0 (通过1)- 7: 深度2, 颜色0 (通过2)- 5: 深度3, 颜色1 (通过4)- 6: 深度3, 颜色1 (通过4)颜色0: 0,4,7 → 3个。颜色1: 1,2,3,5,6 → 5个。max 5。所以 answer[0] 3 5 8 ✓answer[1] 2 5 7 ✓。我的染色计数代码是对的只是手算时数错了。代码实现是正确的。