687. 最长同值路径
题目描述
输入一棵二叉树的根节点 root，用层序数组表示，null 表示空位。
在树中找一条路径，要求路径上所有节点的值都相同。路径可以不经过根，长度按路径包含的边数计算。
返回这类路径的最大长度。树为空或不存在两个相邻同值节点时返回 0。
示例 1
输入：root = [5,4,5,1,1,null,5] 输出：2
解释：右侧三个值为 5 的节点连成一条路径，有 2 条边。
示例 2
输入：root = [1,4,5,4,4,null,5] 输出：2
解释：值为 4 的节点及其两个孩子 4 组成长度为 2 的路径。
数据范围
- 节点数在
[0, 10^4]范围内。 -1000 <= Node.val <= 1000- 树的深度不超过
1000。
解题思路
后序 DFS，arm(node) 返回“从 node 往下、只走一侧、值都等于 node.val 的最长路径边数”。先算左右孩子的 arm；如果左孩子值等于 node.val，左臂 = arm(左) + 1，否则为 0，右侧同理。以 node 为拐点的路径长度是 左臂 + 右臂，用它更新全局答案；向上只能返回较长的一侧。
为什么正确
任何一条同值路径都有唯一的最高点（拐点），在处理拐点时它的长度恰好是左臂 + 右臂，所以会被统计到。
复杂度分析
时间 O(n)，每个节点访问一次；空间 O(h) 递归栈，h 是树高。
易错点
孩子值不同时，对应的臂要置 0，但仍必须递归进去——子树内部可能有更长的同值路径。另外要区分“向上返回的单侧长度 max(l,r)”和“更新答案的两侧之和 l+r”。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
ans = 0
def arm(node):
nonlocal ans
if not node:
return 0
l = arm(node.left)
r = arm(node.right)
l = l + 1 if node.left and node.left.val == node.val else 0
r = r + 1 if node.right and node.right.val == node.val else 0
ans = max(ans, l + r)
return max(l, r)
arm(root)
return ansclass Solution {
int ans = 0;
int arm(TreeNode node) {
if (node == null)
return 0;
int l = arm(node.left);
int r = arm(node.right);
l = (node.left != null && node.left.val == node.val) ? l + 1 : 0;
r = (node.right != null && node.right.val == node.val) ? r + 1 : 0;
ans = Math.max(ans, l + r);
return Math.max(l, r);
}
public int longestUnivaluePath(TreeNode root) {
arm(root);
return ans;
}
}class Solution {
int ans = 0;
int arm(TreeNode* node) {
if (!node)
return 0;
int l = arm(node->left);
int r = arm(node->right);
l = (node->left && node->left->val == node->val) ? l + 1 : 0;
r = (node->right && node->right->val == node->val) ? r + 1 : 0;
ans = max(ans, l + r);
return max(l, r);
}
public:
int longestUnivaluePath(TreeNode* root) {
arm(root);
return ans;
}
};func longestUnivaluePath(root *TreeNode) int {
ans := 0
var arm func(node *TreeNode) int
arm = func(node *TreeNode) int {
if node == nil {
return 0
}
l := arm(node.Left)
r := arm(node.Right)
if node.Left != nil && node.Left.Val == node.Val {
l++
} else {
l = 0
}
if node.Right != nil && node.Right.Val == node.Val {
r++
} else {
r = 0
}
ans = max(ans, l+r)
return max(l, r)
}
arm(root)
return ans
}var longestUnivaluePath = function(root) {
let ans = 0;
const arm = (node) => {
if (!node)
return 0;
let l = arm(node.left);
let r = arm(node.right);
l = node.left && node.left.val === node.val ? l + 1 : 0;
r = node.right && node.right.val === node.val ? r + 1 : 0;
ans = Math.max(ans, l + r);
return Math.max(l, r);
};
arm(root);
return ans;
};function longestUnivaluePath(root: TreeNode | null): number {
let ans = 0;
const arm = (node: TreeNode | null): number => {
if (!node)
return 0;
let l = arm(node.left);
let r = arm(node.right);
l = node.left && node.left.val === node.val ? l + 1 : 0;
r = node.right && node.right.val === node.val ? r + 1 : 0;
ans = Math.max(ans, l + r);
return Math.max(l, r);
};
arm(root);
return ans;
}