LeetCode 题解工作台
好路径的数目
给你一棵 n 个节点的树（连通无向无环的图），节点编号从 0 到 n - 1 且恰好有 n - 1 条边。 给你一个长度为 n 下标从 0 开始的整数数组 vals ，分别表示每个节点的值。同时给你一个二维整数数组 edges ，其中 edges[i] = [a i , b i ] 表示节点 a i…
6
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
要保证路径起点（终点）大于等于路径上的所有点，因此我们可以考虑先把所有点按值从小到大排序，然后再进行遍历，添加到连通块中，具体如下： 当遍历到点 时， 对于小于等于 的邻接点 来说，若二者不在同一个连通块，则可以合并，并且可以以点 所在的连通块中所有值为 的点为起点，以点 所在的连通块中所有值为 的点为终点，两种点的个数的乘积即为加入点 时对答案的贡献。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一棵 n 个节点的树（连通无向无环的图），节点编号从 0 到 n - 1 且恰好有 n - 1 条边。
给你一个长度为 n 下标从 0 开始的整数数组 vals ，分别表示每个节点的值。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。
一条 好路径 需要满足以下条件：
- 开始节点和结束节点的值 相同 。
- 开始节点和结束节点中间的所有节点值都 小于等于 开始节点的值（也就是说开始节点的值应该是路径上所有节点的最大值）。
请你返回不同好路径的数目。
注意，一条路径和它反向的路径算作 同一 路径。比方说， 0 -> 1 与 1 -> 0 视为同一条路径。单个节点也视为一条合法路径。
示例 1：
输入：vals = [1,3,2,1,3], edges = [[0,1],[0,2],[2,3],[2,4]] 输出：6 解释：总共有 5 条单个节点的好路径。 还有 1 条好路径：1 -> 0 -> 2 -> 4 。 （反方向的路径 4 -> 2 -> 0 -> 1 视为跟 1 -> 0 -> 2 -> 4 一样的路径） 注意 0 -> 2 -> 3 不是一条好路径，因为 vals[2] > vals[0] 。
示例 2：
输入：vals = [1,1,2,2,3], edges = [[0,1],[1,2],[2,3],[2,4]] 输出：7 解释：总共有 5 条单个节点的好路径。 还有 2 条好路径：0 -> 1 和 2 -> 3 。
示例 3：
输入：vals = [1], edges = [] 输出：1 解释：这棵树只有一个节点，所以只有一条好路径。
提示：
n == vals.length1 <= n <= 3 * 1040 <= vals[i] <= 105edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biedges表示一棵合法的树。
解题思路
方法一：排序 + 并查集
要保证路径起点（终点）大于等于路径上的所有点，因此我们可以考虑先把所有点按值从小到大排序，然后再进行遍历，添加到连通块中，具体如下：
当遍历到点 时， 对于小于等于 的邻接点 来说，若二者不在同一个连通块，则可以合并，并且可以以点 所在的连通块中所有值为 的点为起点，以点 所在的连通块中所有值为 的点为终点，两种点的个数的乘积即为加入点 时对答案的贡献。
时间复杂度 。
class Solution:
def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
g[b].append(a)
n = len(vals)
p = list(range(n))
size = defaultdict(Counter)
for i, v in enumerate(vals):
size[i][v] = 1
ans = n
for v, a in sorted(zip(vals, range(n))):
for b in g[a]:
if vals[b] > v:
continue
pa, pb = find(a), find(b)
if pa != pb:
ans += size[pa][v] * size[pb][v]
p[pa] = pb
size[pb][v] += size[pa][v]
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n log n + n α(n)) due to sorting nodes and performing near-constant-time union-find operations. Space complexity is O(n) for union-find arrays and hash maps used to count nodes per component. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask if the candidate can process nodes in order of increasing value.
- question_mark
Check whether the candidate tracks counts per connected component to avoid double-counting.
- question_mark
Probe if the candidate correctly handles single-node paths as part of the total.
常见陷阱
外企场景- error
Merging components without considering value order, which leads to invalid good paths.
- error
Forgetting to count single-node paths as valid good paths.
- error
Overcounting paths by not tracking identical-value nodes separately within components.
进阶变体
外企场景- arrow_right_alt
Count good paths where the minimum value along the path equals the endpoint values instead of the maximum.
- arrow_right_alt
Allow weighted edges and count good paths where the maximum node value does not exceed a threshold.
- arrow_right_alt
Compute good paths in a forest rather than a single tree.