LeetCode 题解工作台
最长同值路径
给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。 两个节点之间的路径长度 由它们之间的边数表示。 示例 1: 输入： root = [5,4,5,1,1,5] 输出： 2 示例 2: 输入： root = [1,4,5…
3
题型
8
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们设计一个函数 ，表示以 节点作为路径的其中一个端点，向下延伸的最长同值路径长度。 在 中，我们首先递归调用 和 ，得到两个返回值 和 。这两个返回值分别代表了以 节点的左孩子和右孩子为路径的其中一个端点，向下延伸的最长同值路径长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。
两个节点之间的路径长度 由它们之间的边数表示。
示例 1:
输入：root = [5,4,5,1,1,5] 输出：2
示例 2:
输入：root = [1,4,5,4,4,5] 输出：2
提示:
- 树的节点数的范围是
[0, 104] -1000 <= Node.val <= 1000- 树的深度将不超过
1000
解题思路
方法一：DFS
我们设计一个函数 ，表示以 节点作为路径的其中一个端点，向下延伸的最长同值路径长度。
在 中，我们首先递归调用 和 ，得到两个返回值 和 。这两个返回值分别代表了以 节点的左孩子和右孩子为路径的其中一个端点，向下延伸的最长同值路径长度。
如果 存在左孩子且 ，那么在 的左孩子为路径的其中一个端点，向下延伸的最长同值路径长度应为 ；否则，这个长度为 。如果 存在右孩子且 ，那么在 的右孩子为路径的其中一个端点，向下延伸的最长同值路径长度应为 ；否则，这个长度为 。
在递归调用完左右孩子之后，我们更新答案为 ，即以 为端点的路径经过 的最长同值路径长度。
最后， 函数返回以 为端点的向下延伸的最长同值路径长度，即 。
在主函数中，我们调用 ，即可得到答案。
时间复杂度 ，空间复杂度 。其中 为二叉树的节点个数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
def dfs(root: Optional[TreeNode]) -> int:
if root is None:
return 0
l, r = dfs(root.left), dfs(root.right)
l = l + 1 if root.left and root.left.val == root.val else 0
r = r + 1 if root.right and root.right.val == root.val else 0
nonlocal ans
ans = max(ans, l + r)
return max(l, r)
ans = 0
dfs(root)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N) because every node is visited once during DFS. Space complexity is O(N) due to recursion stack in the worst case of a skewed tree. |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Look for recognition that the path length is counted in edges, not nodes.
- question_mark
Check if the candidate correctly handles paths that do not pass through the root.
- question_mark
Expect use of DFS with state propagation to track continuous univalue segments.
常见陷阱
外企场景- error
Counting nodes instead of edges leads to off-by-one errors.
- error
Failing to combine left and right paths at a node may miss the actual maximum path.
- error
Not resetting counts on value mismatch can inflate path length incorrectly.
进阶变体
外企场景- arrow_right_alt
Compute the longest path for a specific value rather than any univalue path.
- arrow_right_alt
Find the longest path in an n-ary tree where nodes share the same value.
- arrow_right_alt
Return all paths with maximum length instead of just the length.