Last updated on July 19th, 2024 at 11:32 pm

Here, We see Longest Univalue Path LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Hash Table

Companies

LinkedIn

Level of Question

Medium

Longest Univalue Path LeetCode Solution

Problem Statement

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.

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).

1. Longest Univalue Path Leetcode Solution C++

class Solution {
public:
    int longestUnivaluePath(TreeNode* root) {
        int maxlen = 0;
        DFS(root, maxlen);
        return maxlen;
    }
    int DFS(TreeNode* root, int& maxlen){
        if(!root) return 0;
        int left = DFS(root->left, maxlen);
        int right = DFS(root->right, maxlen);
        if(!root->left || root->left->val != root->val) left = 0;
        if(!root->right || root->right->val != root->val) right = 0;
        maxlen = max(maxlen, left + right);
        return max(left, right) + 1;
    }
};

2. Longest Univalue Path Leetcode Solution Java

class Solution 
{
    private int Lpath= 0;
    public int longestUnivaluePath(TreeNode root) 
    {
        pathCalculator(root); 
        return  Lpath;
    }
    private int pathCalculator(TreeNode root)
    {
       if(root == null)
          return 0;
       int left= pathCalculator(root.left);
       int right= pathCalculator(root.right);
       int Tleft= 0, Tright= 0;
       if(root.left != null && root.left.val == root.val)
          Tleft+= left + 1;
       if(root.right != null && root.right.val == root.val)
          Tright+= right+ 1;
       Lpath= Math.max(Lpath, Tleft + Tright);
       return Math.max(Tleft, Tright);
    }
}

3. Longest Univalue Path Solution JavaScript

var longestUnivaluePath = function(root) {
   let level = 0 
   function helper( parent, current) {
		if (current === null) return 0
		let left = helper(current.val, current.left)
		let right = helper(current.val, current.right)
		level = Math.max(level, left + right)
		return current.val === parent ? Math.max(left, right) + 1 : 0
   }
   if (root !== null) helper(root.val, root)
   return level
}

4. Longest Univalue Path Solution Python

class Solution(object):
    def longestUnivaluePath(self, root):
        def dfs(node, prev_val):
            if node is None:
                return 0
            left=dfs(node.left, node.val)
            right=dfs(node.right, node.val)
            self.max_val=max(self.max_val, left+right)
            if node.val==prev_val:
                return max(left, right)+1
            return 0
        self.max_val=0
        if root is None:
            return 0
        dfs(root,root.val)
        return self.max_val