algoadvance

Leetcode 687. Longest Univalue Path

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.

Clarifying Questions

  1. Can the binary tree contain negative values?
    • Yes, the binary tree can contain any integer values.
  2. Are there any constraints on the tree’s size (number of nodes)?
    • The number of nodes in the tree is in the range [0, 10^4].
  3. Should we consider paths that go backtracking, i.e., a node can be revisited?
    • No, each node can only be used once in the path.

Strategy

  1. Traversal and Path Calculation: We will perform a DFS traversal on the tree. During the traversal, for each node, we will calculate the longest path in the left and right subtrees that continue the univalue path.
  2. Update Path Length: If the left or right child has the same value as the current node, we can include that child in the path length calculation.
  3. Track Maximum Path: Maintain a variable to keep track of the maximum path length encountered during the traversal.
  4. Return Result: The algorithm will return the maximum path length found.

Detailed Steps:

  1. DFS Function: We’ll define a helper function that performs DFS. The function will return the length of the longest univalue path starting from the current node and update the global maximum path length.
  2. Comparison of Values: While traversing, if a child node’s value matches the current node’s value, we extend the path length considering that child.
  3. Edge Counting: We count the edges in the path, so for a node with both left and right children having the same value, the total number of edges would be the sum of the edges in the left and right path plus the edge connecting them to the current node.

Code

#include <iostream>
#include <algorithm>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int longestUnivaluePath(TreeNode* root) {
        maxPathLength = 0;  // Initialize the maximum path length
        dfs(root);
        return maxPathLength;
    }
    
private:
    int maxPathLength;
    
    int dfs(TreeNode* node) {
        if (node == nullptr) return 0;
        
        // Recursively get the longest univalue path in the left and right subtrees
        int leftPath = dfs(node->left);
        int rightPath = dfs(node->right);
        
        int left = 0, right = 0;
        
        // If left child exists and has the same value, include it in the path
        if (node->left && node->left->val == node->val) {
            left = leftPath + 1;
        }
        
        // If right child exists and has the same value, include it in the path
        if (node->right && node->right->val == node->val) {
            right = rightPath + 1;
        }
        
        // The longest path through the current node is the sum of left and right paths
        maxPathLength = std::max(maxPathLength, left + right);
        
        // Return the longest one-side path
        return std::max(left, right);
    }
};

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI