[LeetCode 687]最长同值路径
题目描述
给定一个二叉树的 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
思路分析
1.dfs的返回值是什么？
如图，对于根节点而言，需要求的是
a.左子树单侧最长路径，也就是max(L1,R1)
b.右子树单侧最长路径，也就是max(L2,R2)
c.所以根据以上描述，dfs返回的应该是当前节点单侧最长路径长度，对于上图来说，左孩子返回的是max(L1,R1) + 1，右孩子返回的是max(L2,R2) + 1
d.如果孩子和根节点的值不同，则返回0！
2.对于每个节点如何求以当前节点的最长路径？
L + R就是要求的路径长度
3.将上述两个逻辑分析清楚之后，代码就好写了
代码：
class Solution {
public:
int res = 0;
int dfs(TreeNode* root){
if(!root) return 0;
int l = dfs(root->left), r = dfs(root->right);
//如果孩子节点的值与父节点值不一样，说明延伸不出去，长度为0
if(!root->left || root->val != root->left->val) l = 0;
if(!root->right || root->val != root->right->val) r = 0;
//计算以当前节点为根节点的最长同值路径
res = max(res, l + r);
//返回值是单侧的路径长度+1
return max(l, r) + 1;
}
int longestUnivaluePath(TreeNode* root) {
if(!root) return 0;
dfs(root);
return res;
}
};