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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.