LeetCode 题解工作台
最长特殊路径
给你一棵根节点为节点 0 的无向树，树中有 n 个节点，编号为 0 到 n - 1 ，这棵树通过一个长度为 n - 1 的二维数组 edges 表示，其中 edges[i] = [u i , v i , length i ] 表示节点 u i 和 v i 之间有一条长度为 length i 的边。同…
5
题型
0
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一棵根节点为节点 0 的无向树，树中有 n 个节点，编号为 0 到 n - 1 ，这棵树通过一个长度为 n - 1 的二维数组 edges 表示，其中 edges[i] = [ui, vi, lengthi] 表示节点 ui 和 vi 之间有一条长度为 lengthi 的边。同时给你一个整数数组 nums ，其中 nums[i] 表示节点 i 的值。
特殊路径 指的是树中一条从祖先节点 往下 到后代节点且经过节点的值 互不相同 的路径。
注意 ，一条路径可以开始和结束于同一节点。
请你返回一个长度为 2 的数组 result ，其中 result[0] 是 最长 特殊路径的 长度 ，result[1] 是所有 最长特殊路径中的 最少 节点数目。
示例 1：
输入：edges = [[0,1,2],[1,2,3],[1,3,5],[1,4,4],[2,5,6]], nums = [2,1,2,1,3,1]
输出：[6,2]
解释：
下图中，nums 所代表节点的值用对应颜色表示。
最长特殊路径为 2 -> 5 和 0 -> 1 -> 4 ，两条路径的长度都为 6 。所有特殊路径里，节点数最少的路径含有 2 个节点。
示例 2：
输入：edges = [[1,0,8]], nums = [2,2]
输出：[0,1]
解释：
最长特殊路径为 0 和 1 ，两条路径的长度都为 0 。所有特殊路径里，节点数最少的路径含有 1 个节点。
提示：
2 <= n <= 5 * 104edges.length == n - 1edges[i].length == 30 <= ui, vi < n1 <= lengthi <= 103nums.length == n0 <= nums[i] <= 5 * 104- 输入保证
edges表示一棵合法的树。
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexity depend on DFS traversal. Each node is visited once, and the hash set tracks unique values along paths, making worst-case space O(n) and time O(n) if each path is unique. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you maintain uniqueness along the DFS path using a hash structure?
- question_mark
Can you efficiently track path lengths and node counts simultaneously?
- question_mark
Have you considered how array scanning and edge mapping affect traversal speed?
常见陷阱
外企场景- error
Failing to reset the hash set when backtracking leads to incorrect uniqueness checks.
- error
Not updating the minimum node count for multiple longest paths.
- error
Incorrectly mapping edges to children in the tree array structure.
进阶变体
外企场景- arrow_right_alt
Compute longest special path for trees with weighted or unweighted edges.
- arrow_right_alt
Find the longest downward path where node values satisfy a specific condition, not just uniqueness.
- arrow_right_alt
Determine the longest path starting at any node, not necessarily the root.