Given the root of a binary tree, return 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.

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

&nbsp;
Example 1:

Input: root = [5,4,5,1,1,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 5).


Example 2:

Input: root = [1,4,5,4,4,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 4).


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [0, 104].
	-1000 &lt;= Node.val &lt;= 1000
	The depth of the tree will not exceed 1000.


class Solution:
	max_path=0
	def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
		self.dfs(root);
		return self.max_path

	def dfs(self,root):
		if root is None:return 0
		left=self.dfs(root.left)
		right=self.dfs(root.right)

		if root.left  and  root.left.val == root.val:
			leftPath=left+1
		else:
			leftPath=0

		if root.right and  root.right.val == root.val:
			rightPath=right+1
		else:
			rightPath=0

		self.max_path = max(self.max_path, leftPath + rightPath)
		return max(leftPath, rightPath)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxLen = 0;
    public int longestUnivaluePath(TreeNode root) {
        lup(root);
        return maxLen;
    }
    public int lup(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = lup(root.left);
        int right = lup(root.right);
        int leftMax = 0;
        int rightMax = 0;
        if (root.left != null && root.val == root.left.val) {
            leftMax = left + 1;
        }
        if (root.right != null && root.val == root.right.val) {
            rightMax = right + 1;
        }
        maxLen = Math.max(maxLen, leftMax + rightMax);
        return Math.max(leftMax, rightMax);
    }
}
class Solution {
public:
    int maxlen=0;
    pair<int,int> util(TreeNode* root,int val ){
        if(!root)
            return {0,-1001};

        // in pair we will the first part will return the no nodes ,
        //and in the second part we will return the value associated with it

        pair<int,int> l=util(root->left,root->val);
        pair<int,int> r=util(root->right,root->val);

        /* now we will check whether the value coming from
        the left subtree or(&) right subtree is equal to the
        value of the current node

         if equal to both the left && right subtree, then the length returned
        will be max of the left & right subtree , becuase ATQ, we have to
        return the longest path where each node in the path has the same
        value , therefore from the current node we can travel to either the
        left or right subtree , but the maxlength can be l.first+r.first+1 ,
        because we can travel from the leftmost node through the current
        node to the rightmost node , which will be a valid path , therefore
        we will compare this with the maxlength

        */
        if(l.second==root->val && r.second==root->val){
          maxlen=max(maxlen,l.first+r.first+1);
          return {max(l.first,r.first)+1,root->val};

        }

        // now similary checking for all the other nodes:

        else if(l.second==root->val){
            maxlen=max(maxlen,l.first+1);
            return {l.first+1,root->val};
        }
        else if(r.second==root->val){
            maxlen=max(maxlen,r.first+1);
            return {r.first+1,root->val};
        }
        else{
            return {1,root->val};
        }

    }
    int longestUnivaluePath(TreeNode* root) {
        if(!root)
            return 0;
        util(root,root->val);
        return max(maxlen-1,0);

    }
};
var longestUnivaluePath = function(root) {
	let max = 0;
	const dfs = (node = root, parentVal) => {
		if (!node) return 0;
		const { val, left, right } = node;
		const leftPath = dfs(left, val);
		const rightPath = dfs(right, val);

		max = Math.max(max, leftPath + rightPath);
		return val === parentVal 
			? Math.max(leftPath, rightPath) + 1
			: 0;
	};

	dfs();
	return max;
};
Longest Univalue Path