Kimi LeetCode 3425. 最长特殊路径 Python3实现
以下是 LeetCode 3425. 最长特殊路径 的 Python3 实现。
---
解题思路
这道题的核心是 DFS + 滑动窗口（树上的双指针），时间复杂度 O(n)，空间复杂度 O(n)。
关键观察
1. 特殊路径的定义：路径上所有节点的值互不相同。这等价于"无重复元素的最长子数组"问题在树上的扩展。
2. 为什么用滑动窗口？ 从根节点出发 DFS，维护当前路径上的节点值集合。当遇到重复值时，需要收缩左边界，直到没有重复值为止。这和数组上的"无重复元素最长子数组"问题本质相同。
3. 具体实现：
- `prefix` 数组：记录从根到当前节点的路径长度前缀和，`prefix[i]` 表示深度为 `i` 的节点到根的路径长度
- `lastSeenDepth`：字典，记录每个节点值最后出现的深度
- `leftBoundary`：当前窗口的左边界深度，确保 `[leftBoundary, currentDepth]` 内无重复值
4. 路径长度计算：`length = prefix[currentDepth] - prefix[leftBoundary]`，节点数 = `currentDepth - leftBoundary`
---
Python3 完整代码
```python
from typing import List
class Solution:
def longestSpecialPath(self, edges: List[List[int]], nums: List[int]) -> List[int]:
n = len(nums)
# 建图：邻接表，存储 (邻居节点, 边权)
graph = [[] for _ in range(n)]
for u, v, w in edges:
graph[u].append((v, w))
graph[v].append((u, w))
# 答案变量
maxLength = 0
minNodes = 1
# prefix[i] = 从根节点到深度为 i 的节点的路径长度
prefix = [0]
# lastSeenDepth[val] = 节点值 val 最后出现的深度
lastSeenDepth = {}
def dfs(u: int, prev: int, leftBoundary: int) -> None:
nonlocal maxLength, minNodes
# 记录当前节点值之前出现的深度
prevDepth = lastSeenDepth.get(nums[u], 0)
# 更新当前节点值的最后出现深度
lastSeenDepth[nums[u]] = len(prefix)
# 收缩左边界：确保 [leftBoundary, currentDepth] 内无重复值
leftBoundary = max(leftBoundary, prevDepth)
# 计算当前路径的长度和节点数
length = prefix[-1] - prefix[leftBoundary]
nodes = len(prefix) - leftBoundary
# 更新答案：优先更长路径，长度相同时更少节点数
if length > maxLength or (length == maxLength and nodes < minNodes):
maxLength = length
minNodes = nodes
# 遍历所有子节点
for v, w in graph[u]:
if v == prev:
continue
# 将子节点加入路径
prefix.append(prefix[-1] + w)
dfs(v, u, leftBoundary)
prefix.pop() # 回溯
# 回溯：恢复当前节点值的最后出现深度
lastSeenDepth[nums[u]] = prevDepth
# DFS 从根节点 0 开始
dfs(0, -1, 0)
return [maxLength, minNodes]
```
---
测试验证
输入 输出 说明
`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]` 最长路径 2→5（长度6，2个节点）和 0→1→4（长度6，3个节点），取最少节点数 2
`edges=[[1,0,8]], nums=[2,2]` `[0, 1]` 两节点值相同，只能选单个节点
`edges=[], nums=[5]` `[0, 1]` 单节点
`edges=[[0,1,1],[1,2,1],[2,3,1]], nums=[1,2,3,4]` `[3, 4]` 链状树，无重复值
`edges=[[0,1,1],[0,2,1],[1,3,1],[1,4,1]], nums=[1,2,1,3,4]` `[2, 3]` 有重复值需要收缩窗口
下载完整代码：[leetcode_3425.py](sandbox:///mnt/agents/output/leetcode_3425.py)