class Solution {
public:
int helper(TreeNode* root, int val)
{
if(!root  root>val != val) return 0;
return 1 + max(helper(root>left,val),helper(root>right,val));
}
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));
}
};
Concise DFS solution with no global variables


@i9r0k cool! I implemented the same algorithm! Here's my take:
class Solution { public: int longestUnivaluePath(TreeNode* root) { return joint(root); } int joint(TreeNode* n) { if (!n) return 0; return max( max(joint(n>left), joint(n>right)), path(n>left, n>val) + path(n>right, n>val) ); } int path(TreeNode* n, int k) { if (!n  n>val != k) return 0; return 1 + max(path(n>left, k), path(n>right, k)); } };

I like this idea because it does not have any global vars. Here is the java version:
public int longestUnivaluePath(TreeNode root) { if (root == null) return 0; int sub = Math.max(longestUnivaluePath(root.left), longestUnivaluePath(root.right)); return Math.max(sub, helper(root.left, root.val) + helper(root.right, root.val)); } private int helper(TreeNode node, int val) { if (node == null  node.val != val) return 0; return 1 + Math.max(helper(node.left, val), helper(node.right, val)); }





@anand1604 Yes, you can check the second example in the problem description. The longest path is 444. The valid path can go up and down.