LeetCode 题解工作台
连接两棵树后最大目标节点数目 I
有两棵 无向 树，分别有 n 和 m 个树节点。两棵树中的节点编号分别为 [0, n - 1] 和 [0, m - 1] 中的整数。 给你两个二维整数 edges1 和 edges2 ，长度分别为 n - 1 和 m - 1 ，其中 edges1[i] = [a i , b i ] 表示第一棵树中节…
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
根据题目描述，要使得节点 的目标节点数目最大，对于第 个节点，我们一定会选择该节点与第二棵树中的其中一个节点 相连，因此，节点 的目标节点数可以分成两部分计算： - 在第一棵树中，从节点 出发，深度不超过 的节点数目；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
有两棵 无向 树，分别有 n 和 m 个树节点。两棵树中的节点编号分别为[0, n - 1] 和 [0, m - 1] 中的整数。
给你两个二维整数 edges1 和 edges2 ，长度分别为 n - 1 和 m - 1 ，其中 edges1[i] = [ai, bi] 表示第一棵树中节点 ai 和 bi 之间有一条边，edges2[i] = [ui, vi] 表示第二棵树中节点 ui 和 vi 之间有一条边。同时给你一个整数 k 。
如果节点 u 和节点 v 之间路径的边数小于等于 k ，那么我们称节点 u 是节点 v 的 目标节点 。注意 ，一个节点一定是它自己的 目标节点 。
请你返回一个长度为 n 的整数数组 answer ，answer[i] 表示将第一棵树中的一个节点与第二棵树中的一个节点连接一条边后，第一棵树中节点 i 的 目标节点 数目的 最大值 。
注意 ，每个查询相互独立。意味着进行下一次查询之前，你需要先把刚添加的边给删掉。
示例 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]], k = 2
输出：[9,7,9,8,8]
解释：
- 对于
i = 0，连接第一棵树中的节点 0 和第二棵树中的节点 0 。 - 对于
i = 1，连接第一棵树中的节点 1 和第二棵树中的节点 0 。 - 对于
i = 2，连接第一棵树中的节点 2 和第二棵树中的节点 4 。 - 对于
i = 3，连接第一棵树中的节点 3 和第二棵树中的节点 4 。 - 对于
i = 4，连接第一棵树中的节点 4 和第二棵树中的节点 4 。
示例 2：
输入：edges1 = [[0,1],[0,2],[0,3],[0,4]], edges2 = [[0,1],[1,2],[2,3]], k = 1
输出：[6,3,3,3,3]
解释：
对于每个 i ，连接第一棵树中的节点 i 和第二棵树中的任意一个节点。
提示：
2 <= n, m <= 1000edges1.length == n - 1edges2.length == m - 1edges1[i].length == edges2[i].length == 2edges1[i] = [ai, bi]0 <= ai, bi < nedges2[i] = [ui, vi]0 <= ui, vi < m- 输入保证
edges1和edges2都表示合法的树。 0 <= k <= 1000
解题思路
方法一：枚举 + DFS
根据题目描述，要使得节点 的目标节点数目最大，对于第 个节点，我们一定会选择该节点与第二棵树中的其中一个节点 相连，因此，节点 的目标节点数可以分成两部分计算：
- 在第一棵树中，从节点 出发，深度不超过 的节点数目；
- 在第二棵树中，从任意节点 出发，深度不超过 的节点数目，取最大值。
因此，我们可以先计算第二棵树中每个节点的深度不超过 的节点数目，然后枚举第一棵树中的每个节点 ，计算上述两部分的和，取最大值即可。
时间复杂度 ，空间复杂度 。其中 和 分别为两棵树的节点数。
class Solution:
def maxTargetNodes(
self, edges1: List[List[int]], edges2: List[List[int]], k: int
) -> List[int]:
def build(edges: List[List[int]]) -> List[List[int]]:
n = len(edges) + 1
g = [[] for _ in range(n)]
for a, b in edges:
g[a].append(b)
g[b].append(a)
return g
def dfs(g: List[List[int]], a: int, fa: int, d: int) -> int:
if d < 0:
return 0
cnt = 1
for b in g[a]:
if b != fa:
cnt += dfs(g, b, a, d - 1)
return cnt
g2 = build(edges2)
m = len(edges2) + 1
t = max(dfs(g2, i, -1, k - 1) for i in range(m))
g1 = build(edges1)
n = len(edges1) + 1
return [dfs(g1, i, -1, k) + t for i in range(n)]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n^2 + m^2) |
| 空间 | O(n + m) |
面试官常问的追问
外企场景- question_mark
Ability to efficiently implement DFS/BFS for tree traversal
- question_mark
Skill in tracking and updating node states during traversal
- question_mark
Understanding of tree connection and maximum reachable node calculations
常见陷阱
外企场景- error
Inefficient traversal leading to excessive recomputation of reachable nodes
- error
Forgetting to update reachable node counts correctly during the traversal
- error
Overlooking edge cases such as disconnected nodes or multiple valid connections
进阶变体
外企场景- arrow_right_alt
Consider trees of different sizes, which may affect the time complexity of the solution.
- arrow_right_alt
Modify the problem to connect nodes based on different distance constraints.
- arrow_right_alt
Extend the problem to include multiple trees and their connections.