当前位置：首页 > news >正文

Kimi LeetCode 3373. 连接两棵树后最大目标节点数目 II Java实现

news 2026/6/25 16:45:39

LeetCode 3373. 连接两棵树后最大目标节点数目 II — Java 实现

题目描述

有两棵无向树，分别有 `n` 和 `m` 个节点。给定两棵树的边 `edges1` 和 `edges2`。

如果节点 `u` 和节点 `v` 之间路径的边数是偶数，则称 `u` 是 `v` 的目标节点。一个节点一定是它自己的目标节点。

返回长度为 `n` 的数组 `answer`，`answer[i]` 表示将第一棵树中节点 `i` 与第二棵树中某个节点连接一条边后，第一棵树中节点 `i` 的目标节点数目的最大值。

核心思路：黑白染色法

树是二分图，可以用 0/1 染色来区分节点深度的奇偶性：

- 相邻节点颜色不同（0 和 1 交替）
- 相同颜色的节点之间距离为偶数（目标节点关系）
- 不同颜色的节点之间距离为奇数

所以对每棵树染色后，统计颜色 0 和颜色 1 的节点数量即可。

对于第一棵树的节点 `i`：
- 树1中的目标节点 = 与 `i` 同色的节点数
- 连接树2后，树2中的目标节点 = 可以选择树2中颜色更多的那一类（通过选择连接树2中对应颜色的节点，使距离为偶数）

Java 实现

```java
import 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;

// 构建邻接表
List<List<Integer>> 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（颜色0）
int 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(List<List<Integer>> 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;
}
}
```

另一种更简洁的写法（使用 BFS）

```java
import 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;
List<Integer>[] 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];
Queue<int[]> 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数)`

验证示例

示例 1：`edges1 = [[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个，max=4。但答案中节点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` 还是不对...

哦，我数错了。重新看树1：`edges1 = [[0,1],[0,2],[2,3],[2,4]]`
- 0: 深度0, 颜色0
- 1: 深度1, 颜色1
- 2: 深度1, 颜色1
- 3: 深度2, 颜色0
- 4: 深度2, 颜色0