grid47 Exploring patterns and algorithms
Aug 30, 2024
8 min read
Solution to LeetCode 687: Longest Univalue Path Problem
You are given the root of a binary tree. The task is to find the length of the longest path in the tree where all the nodes in the path have the same value. The path can be anywhere in the tree, not necessarily passing through the root. The path length is determined by the number of edges between the nodes.
Problem
Approach
Steps
Complexity
Input: The input consists of a binary tree represented by its root node.
Example: root = [3, 2, 3, 1, 3, null, 3]
Constraints:
• 0 <= Number of nodes <= 10^4
• -1000 <= Node.val <= 1000
• Tree depth will not exceed 1000
Output: Return the length of the longest path in the binary tree where all nodes in the path have the same value. The path length is measured by the number of edges.
Example: For root = [3, 2, 3, 1, 3, null, 3], the output is 3.
Constraints:
• The output should be an integer representing the length of the longest path.
Goal: To find the longest path where all nodes have the same value in the binary tree.
Steps:
• 1. Traverse the tree using DFS to explore the longest path for each node.
• 2. For each node, check if its left and right child nodes have the same value as itself.
• 3. Update the maximum path length encountered during the DFS traversal.
Goal: The problem has constraints ensuring the binary tree is manageable in size and the node values are within a specified range.
Steps:
• The number of nodes is between 0 and 10^4.
• Node values range from -1000 to 1000.
• The tree's depth does not exceed 1000.
Assumptions:
• The binary tree may have a depth of up to 1000 nodes.
• Input: root = [3, 2, 3, 1, 3, null, 3]
• Explanation: The longest path with the same value (i.e., 3) is 3 -> 3 -> 3, which has a length of 3.
• Input: root = [4, 4, 4, 1, 1, null, 4]
• Explanation: The longest path with the same value (i.e., 4) is 4 -> 4 -> 4, which has a length of 2.
Approach: The approach is to use depth-first search (DFS) to traverse the tree and calculate the longest path where all nodes have the same value. We need to explore both left and right subtrees and ensure that the path continues as long as the nodes have the same value.
Observations:
• We need to explore both left and right subtrees for each node to find the longest path where all nodes have the same value.
• DFS is an ideal choice for this problem since we are required to explore all possible paths in the binary tree.
Steps:
• 1. Initialize a variable `maxi` to track the longest path found so far.
• 2. Implement a DFS function to explore each node and its left and right subtrees.
• 3. For each node, check if its children have the same value as itself and update the path length accordingly.
• 4. Return the maximum path length after the DFS traversal is complete.
Empty Inputs:
• If the tree is empty, return 0.
Large Inputs:
• The solution should handle large trees efficiently with up to 10^4 nodes.
Special Values:
• If all nodes have the same value, the path length will be the depth of the tree.
Constraints:
• Ensure the solution works within the constraint that the tree depth will not exceed 1000.
classSolution {
int maxi;
public:int longestUnivaluePath(TreeNode* root) {
maxi =0;
if((root ==NULL) || (root->left ==NULL&& root->right ==NULL) )
return0;
dfs(root);
return maxi;
}
intdfs(TreeNode *root) {
if(root ==NULL) return0;
int l =0, r =0;
int lft = dfs(root->left);
int rgt = dfs(root->right);
if((root->left !=NULL) && (root->left->val == root->val))
l = lft;
if((root->right !=NULL) && (root->right->val == root->val))
r = rgt;
maxi = max(maxi, l + r);
return1+ max(l, r);
}
1 : Class Definition
classSolution {
Define the Solution class where the main logic for finding the longest univalue path will be implemented.
2 : Variable Declaration
int maxi;
Declare the variable 'maxi' to store the maximum length of the univalue path found during the DFS traversal.
3 : Access Modifier
public:
The 'public' access modifier indicates that the following methods and variables are accessible from outside the class.
4 : Method Definition
intlongestUnivaluePath(TreeNode* root) {
Define the 'longestUnivaluePath' method, which accepts a TreeNode 'root' and returns the length of the longest path of nodes with the same value.
5 : Initialize maxi
maxi =0;
Initialize 'maxi' to zero before starting the DFS traversal.
Check if the root is NULL or if the root has no children. If either condition is true, return 0 as no univalue path can exist.
7 : Return 0
return0;
Return 0 if the root node is NULL or a leaf node, as no path is possible.
8 : DFS Call
dfs(root);
Call the DFS helper function to start the depth-first search on the tree.
9 : Return Maxi
return maxi;
After completing the DFS traversal, return the value of 'maxi', which holds the longest univalue path.
10 : Helper Method Definition
intdfs(TreeNode *root) {
Define the 'dfs' method that performs a depth-first search on the tree and returns the length of the longest univalue path starting from the current node.
11 : Base Case Check
if(root ==NULL) return0;
Check if the current node is NULL. If it is, return 0 since there's no univalue path from a NULL node.
12 : Initialize Left and Right
int l =0, r =0;
Initialize two variables, 'l' and 'r', to store the lengths of univalue paths in the left and right subtrees, respectively.
13 : Recursive DFS for Left Subtree
int lft = dfs(root->left);
Recursively call 'dfs' on the left child of the current node and store the result in 'lft'.
14 : Recursive DFS for Right Subtree
int rgt = dfs(root->right);
Recursively call 'dfs' on the right child of the current node and store the result in 'rgt'.
