难度: Medium
给定一个二叉树的 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
Submission
运行时间: 140 ms
内存: 19.5 MB
# 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:
ans = 0
def dfs(node):
if not node:
return 0
nonlocal ans
cur_max = 0
if node.left:
left_max = dfs(node.left)
if node.val == node.left.val:
ans = max(ans, cur_max + left_max + 1)
cur_max = left_max + 1
if node.right:
right_max = dfs(node.right)
if node.val == node.right.val:
ans = max(ans, cur_max + right_max + 1)
cur_max = max(cur_max, right_max + 1)
return cur_max
dfs(root)
return ans
Explain
此题解采用深度优先搜索（DFS）来寻找树中的最长同值路径。首先，定义一个全局变量 `ans` 来存储最大路径的长度。对于每一个节点，使用递归函数 `dfs` 来分别计算其左右子树的最长同值路径长度。如果子节点的值与当前节点的值相同，那么该子树对应的最长同值路径就可以与当前节点连起来构成更长的路径。函数返回该节点的单边最长同值路径长度，即左右子树中较长的那个加上当前节点。通过比较和更新全局变量 `ans`，最终 `dfs` 返回后的 `ans` 值即为题目要求的最长同值路径的长度。
时间复杂度: O(n)
空间复杂度: O(n)
# 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:
ans = 0 # 最长同值路径的长度
def dfs(node):
if not node:
return 0 # 如果当前节点为空，则返回0
nonlocal ans # 引用外部的ans变量
cur_max = 0 # 当前节点的最长同值路径
if node.left: # 如果有左子节点
left_max = dfs(node.left) # 计算左子树的最长同值路径
if node.val == node.left.val: # 如果左子节点的值等于当前节点的值
ans = max(ans, cur_max + left_max + 1) # 更新最长路径长度
cur_max = left_max + 1 # 更新当前最长同值路径
if node.right: # 如果有右子节点
right_max = dfs(node.right) # 计算右子树的最长同值路径
if node.val == node.right.val: # 如果右子节点的值等于当前节点的值
ans = max(ans, cur_max + right_max + 1) # 更新最长路径长度
cur_max = max(cur_max, right_max + 1) # 更新当前最长同值路径
return cur_max # 返回当前节点的最长同值路径长度
dfs(root) # 从根节点开始DFS
return ans # 返回最长同值路径的长度
Explore
在DFS递归函数中，即使左右子节点的值都与当前节点相同，只更新ans一次是因为我们在寻找的是通过当前节点的最长同值路径，这条路径可以从左子节点经过当前节点到右子节点。如果我们更新两次，可能会错误地计算两条分开的路径长度之和，而实际上我们需要的是一条连续路径。因此，我们在计算ans时，考虑的是一个连续路径的最大长度，而不是两条独立路径的长度总和。
在递归函数中，变量cur_max用于记录从当前节点出发向下延伸的单方向最长同值路径的长度。这是通过计算并比较左右子树返回的同值路径长度来实现的。如果子节点的值与当前节点相同，我们会对该子节点返回的路径长度加一（表示包括当前节点在内的路径），然后更新cur_max。如果有两个子节点都与当前节点值相同，cur_max将记录它们中的最大值，确保cur_max总是表示从当前节点出发的最长单方向路径。
如果有多个子节点的值与当前节点相同，选择将cur_max更新为最大的那个路径长度是为了确保我们计算的是最长的单方向路径。这种选择意味着我们在考虑通过当前节点可能形成的最长连续路径时，只考虑了最优的一条路径，这帮助我们避免了重复计算或路径长度的过度估计。这对结果的影响是确保了ans的准确性和最大化，因为ans需要反映树中任何可能的最长同值路径。
在递归结束后返回ans值时，确实需要考虑边界情况。例如，如果树为空（即根节点为null），则不存在任何路径，ans初始值为0，适用于此情况，直接返回0即可。如果树只有一个节点，由于没有子节点，任何通过该节点的同值路径长度也为0。因此，ans的初始值同样适用，并正确反映了这些边界情况的最长同值路径长度。