Leetcode 687. Longest Univalue Path

Problem Explanation

This problem is about finding the longest path in a binary tree where all nodes on the path have the same value. Note that the path does not necessarily have to start at the root node. Basically, we just need to find two nodes with the same value where the number of edges, i.e., the distance between them, is the greatest.

For instance, consider the binary tree from Example 1. Here the longest path with the same value is 5-5 on the right side of the root node, with the length of 2.

The key idea to solve this problem is similar to Depth-First Search (DFS) algorithm. We recursively go through each node and calculate the length of the longest univalue path, i.e., a path where all nodes have the same value. We maintain a global variable ans to keep track of the maximum length encountered so far.

To illustrate this, let's take a smaller example:

1
2
3    1
4   / \
5  1   1
6 / 
71   

Initially we set ans=0. For the leftmost node with value 1, both longestUnivaluePathDownFrom(root->left, ans) and longestUnivaluePathDownFrom(root->right, ans) return 0 because it has no children. The value of ans remains 0.

For the node above it, it has one child with the same value. So, longestUnivaluePathDownFrom(root->left, ans) returns 1 (0 + 1). Then ans becomes 1.

We then recursively calculate for the other nodes and finally get ans=2.

Python Solution

Now, let's see how we can solve this problem in different programming languages.

Here is the Python solution:

1
2python
3# Definition for a binary tree node.
4# class TreeNode:
5#     def __init__(self, val=0, left=None, right=None):
6#     self.val = val
7#     self.left = left
8#     self.right = right
9
10class Solution:
11    def longestUnivaluePath(self, root):
12        self.ans = 0
13        self.longestUnivaluePathDownFrom(root)
14        return self.ans
15
16    def longestUnivaluePathDownFrom(self, root):
17        if root == None:
18            return 0
19
20        left = self.longestUnivaluePathDownFrom(root.left)
21        right = self.longestUnivaluePathDownFrom(root.right)
22        arrowLeft = arrowRight = 0
23
24        if root.left and root.left.val == root.val:
25            arrowLeft = left + 1
26        if root.right and root.right.val == root.val:
27            arrowRight = right + 1
28
29        self.ans = max(self.ans, arrowLeft + arrowRight)
30
31        return max(arrowLeft, arrowRight)

Java Solution

1
2java
3// The definition for a binary tree node.
4// public class TreeNode {
5//     int val;
6//     TreeNode left;
7//     TreeNode right;
8//     TreeNode() {}
9//     TreeNode(int val) { this.val = val; }
10//     TreeNode(int val, TreeNode left, TreeNode right) {
11//         this.val = val;
12//         this.left = left;
13//         this.right = right;
14//     }
15// }
16
17class Solution {
18    private int ans;
19    public int longestUnivaluePath(TreeNode root) {
20        ans = 0;
21        longestUnivaluePathDownFrom(root);
22        return ans;
23    }
24
25    private int longestUnivaluePathDownFrom(TreeNode node) {
26        if (node == null) return 0;
27
28        int left = longestUnivaluePathDownFrom(node.left);
29        int right = longestUnivaluePathDownFrom(node.right);
30
31        int arrowLeft = 0, arrowRight = 0;
32        if (node.left != null && node.left.val == node.val) {
33            arrowLeft += left + 1;
34        }
35        if (node.right != null && node.right.val == node.val) {
36            arrowRight += right + 1;
37        }
38
39        ans = Math.max(ans, arrowLeft + arrowRight);
40
41        return Math.max(arrowLeft, arrowRight);
42    }
43}

JavaScript Solution

1
2javascript
3// Definition for a binary tree node.
4// function TreeNode(val, left, right) {
5//     this.val = (val===undefined ? 0 : val)
6//     this.left = (left===undefined ? null : left)
7//     this.right = (right===undefined ? null : right)
8// }
9
10var longestUnivaluePath = function(root) {
11    let ans = 0;
12    
13    const longestUnivaluePathDownFrom = (root) => {
14        if (root == null) {
15            return 0;
16        }
17        
18        let left = longestUnivaluePathDownFrom(root.left);
19        let right = longestUnivaluePathDownFrom(root.right);
20        let arrowLeft = 0, arrowRight = 0;
21        
22        if (root.left && root.left.val == root.val) {
23            arrowLeft = left + 1;
24        }
25        if (root.right && root.right.val == root.val) {
26            arrowRight = right + 1;
27        }
28        
29        ans = Math.max(ans, arrowLeft + arrowRight);
30        return Math.max(arrowLeft, arrowRight);
31    }
32    longestUnivaluePathDownFrom(root);
33    return ans;
34};
35

C++ Solution

1
2cpp
3// The definition for a binary tree node.
4// struct TreeNode {
5//     int val;
6//     TreeNode *left;
7//     TreeNode *right;
8//     TreeNode() : val(0), left(nullptr), right(nullptr) {}
9//     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10//     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11// };
12
13class Solution {
14public:
15    int longestUnivaluePath(TreeNode* root) {
16        int ans = 0;
17        longestUnivaluePathDownFrom(root, ans);
18        return ans;
19    }
20private:
21    int longestUnivaluePathDownFrom(TreeNode* root, int& ans) {
22        if (root == nullptr)
23            return 0;
24        int left = longestUnivaluePathDownFrom(root->left, ans);
25        int right = longestUnivaluePathDownFrom(root->right, ans);
26        int arrowLeft = 0, arrowRight = 0;
27        
28        if (root->left && root->left->val == root->val)
29            arrowLeft = left + 1;
30        if (root->right && root->right->val == root->val)
31            arrowRight = right + 1;
32        ans = max(ans, arrowLeft + arrowRight);
33        return max(arrowLeft, arrowRight);
34    }
35};

C# Solution

1
2csharp
3// Definition for a binary tree node.
4// public class TreeNode {
5//     public int val;
6//     public TreeNode left;
7//     public TreeNode right;
8//     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
9//         this.val = val;
10//         this.left = left;
11//         this.right = right;
12//     }
13// }
14
15public class Solution {
16    private int ans;
17
18    public int LongestUnivaluePath(TreeNode root) {
19        ans = 0;
20        LongestUnivaluePathDownFrom(root);
21        return ans;
22    }
23
24    private int LongestUnivaluePathDownFrom(TreeNode node) {
25        if (node == null) return 0;
26
27        int left = LongestUnivaluePathDownFrom(node.left);
28        int right = LongestUnivaluePathDownFrom(node.right);
29        int arrowLeft = 0, arrowRight = 0;
30
31        if (node.left != null && node.left.val == node.val) {
32            arrowLeft += left + 1;
33        }
34        if (node.right != null && node.right.val == node.val) {
35            arrowRight += right + 1;
36        }
37
38        ans = Math.Max(ans, arrowLeft + arrowRight);
39
40        return Math.Max(arrowLeft, arrowRight);
41    }
42}

These solutions visit each node in the tree once, which leads to a time complexity of O(N), where N is the number of nodes in the tree.## Ruby Solution

1
2ruby
3# Definition for a binary tree node.
4# class TreeNode
5#     attr_accessor :val, :left, :right
6#     def initialize(val = 0, left = nil, right = nil)
7#         @val = val
8#         @left = left
9#         @right = right
10#     end
11# end
12
13class Solution
14    attr_accessor :ans
15    def longest_univalue_path(root)
16        self.ans = 0
17        longest_univalue_path_down_from(root)
18        return self.ans
19    end
20
21    def longest_univalue_path_down_from(root)
22        return 0 if root.nil?
23
24        left = longest_univalue_path_down_from(root.left)
25        right = longest_univalue_path_down_from(root.right)
26        arrow_left = arrow_right = 0
27
28        if root.left && root.left.val == root.val
29            arrow_left = left + 1
30        end
31        if root.right && root.right.val == root.val
32            arrow_right = right + 1
33        end
34
35        self.ans = [self.ans, arrow_left + arrow_right].max
36
37        return [arrow_left, arrow_right].max
38    end
39end

Go Solution

1
2go
3//Definition for a binary tree node.
4// type TreeNode struct {
5//     Val int
6//     Left *TreeNode
7//     Right *TreeNode
8// }
9
10type Solution struct {
11    ans int
12}
13
14func (s *Solution) longestUnivaluePath(root *TreeNode) int {
15    s.ans = 0
16    s.longestUnivaluePathDownFrom(root)
17    return s.ans
18}
19
20func (s *Solution) longestUnivaluePathDownFrom(root *TreeNode) int {
21    if root == nil {
22        return 0
23    }
24
25    left := s.longestUnivaluePathDownFrom(root.Left)
26    right := s.longestUnivaluePathDownFrom(root.Right)
27    arrowLeft, arrowRight := 0, 0 
28
29    if root.Left != nil && root.Left.Val == root.Val {
30        arrowLeft = left + 1
31    }
32    if root.Right != nil && root.Right.Val == root.Val {
33        arrowRight = right + 1
34    }
35
36    s.ans = max(s.ans, arrowLeft + arrowRight)
37
38    return max(arrowLeft, arrowRight)
39}
40
41func max(a, b int) int {
42    if a > b {
43        return a
44    }
45    return b
46}

TypeScript Solution

1
2typescript
3// Definition for a binary tree node.
4// class TreeNode {
5//     val: number
6//     left: TreeNode | null
7//     right: TreeNode | null
8//     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
9//         this.val = (val===undefined ? 0 : val)
10//         this.left = (left===undefined ? null : left)
11//         this.right = (right===undefined ? null : right)
12//     }
13// }
14
15function longestUnivaluePath(root: TreeNode | null): number {
16    let ans = 0;
17    const dfs = (node: TreeNode | null): number => {
18        if (!node) return 0;
19
20        const left = dfs(node.left);
21        const right = dfs(node.right);
22        let arrowLeft = 0, arrowRight = 0;
23
24        if(node.left && node.left.val === node.val) arrowLeft = left + 1;
25        if (node.right && node.right.val === node.val) arrowRight = right + 1;
26
27        ans = Math.max(ans, arrowLeft + arrowRight);
28        return Math.max(arrowLeft, arrowRight);
29    }
30    dfs(root);
31
32    return ans;
33};

Like the other languages, the Ruby, Go, and Typescript solutions have a time complexity of O(N), where N is the number of nodes in the tree, as each node is visited exactly once.