# 687. Longest Univalue Path

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.

Note: The length of path between two nodes is represented by the number of edges between them.

Example 1:

Input:

``````              5
/ \
4   5
/ \   \
1   1   5
``````

Output:

``````2
``````

Example 2:

Input:

``````              1
/ \
4   5
/ \   \
4   4   5
``````

Output:

``````2
``````

Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

``````      1
/ \
4   5
/ \   \
4   4   5
/
4
``````

``````class Solution {
public:
int longestUnivaluePath(TreeNode* root) {
int res = 0;
helper(root, res);
return res;
}
int helper(TreeNode* node, int& res) {
if (!node) return 0;
int left = helper(node->left, res);
int right = helper(node->right, res);
left = (node->left && node->val == node->left->val) ? left + 1 : 0;
right = (node->right && node->val == node->right->val) ? right + 1 : 0;
res = max(res, left + right);
return max(left, right);
}
};
``````

``````class Solution {
public:
int longestUnivaluePath(TreeNode* root) {
int res = 0;
if (root) helper(root, root->val, res);
return res;
}
int helper(TreeNode* node, int parent, int& res) {
if (!node) return 0;
int left = helper(node->left, node->val, res);
int right = helper(node->right, node->val, res);
res = max(res, left + right);
if (node->val == parent) return max(left, right) + 1;
return 0;
}
};
``````

``````class Solution {
public:
int longestUnivaluePath(TreeNode* root) {
if (!root) return 0;
int sub = max(longestUnivaluePath(root->left), longestUnivaluePath(root->right));
return max(sub, helper(root->left, root->val) + helper(root->right, root->val));
}
int helper(TreeNode* node, int parent) {
if (!node || node->val != parent) return 0;
return 1 + max(helper(node->left, node->val), helper(node->right, node->val));
}
};
``````

Binary Tree Maximum Path Sum

Count Univalue Subtrees

https://leetcode.com/problems/longest-univalue-path/

https://leetcode.com/problems/longest-univalue-path/discuss/108136/JavaC%2B%2B-Clean-Code

https://leetcode.com/problems/longest-univalue-path/discuss/108175/java-solution-with-global-variable

https://leetcode.com/problems/longest-univalue-path/discuss/108146/Concise-DFS-solution-with-no-global-variables

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation