Longest Univalue Path

class Solution {
public:
    int longestPathResult;

    int calculate(TreeNode* node, int prevVal) {
        if (node == NULL) {
            return 0;
        }

        int leftPath = calculate(node->left, node->val);
        int rightPath = calculate(node->right, node->val);

        longestPathResult = max(longestPathResult, leftPath + rightPath);

        // Path count is zero if node value doesn't match with its parent value.
        // We include the node itself in the count by adding 1.
        return node->val == prevVal ? max(leftPath, rightPath) + 1 : 0;
    }

    int longestUnivaluePath(TreeNode* root) {
        // Initial parent value is set as -1, assuming no node value is negative.
        calculate(root, -1);
        
        return longestPathResult;
    }
};

The provided C++ solution addresses the problem of finding the longest univalue path in a binary tree. The univalue path refers to the longest path in which all nodes have the same value. The solution features a class Solution with a member function longestUnivaluePath.

• The class contains an integer member longestPathResult used to store the maximum length of any univalue path found during the recursive traversal of the tree.

• The function calculate is a recursive helper function designed to traverse the binary tree:

  • It accepts two parameters: a pointer to the current tree node node and the integer prevVal, which holds the value of the parent node.
  • The base case checks if the node pointer is NULL, returning 0 to indicate no path continuation.
  • For the left and right children of the current node, the function recursively calls itself, updating paths if the current node and its children have the same value.
  • The resultant path lengths for left and right sub-trees are evaluated, and the longestPathResult is updated accordingly to store the maximum length found.
  • The function returns the length of the longest univalue path including this node if the value matches with its parent; otherwise, returns zero.

• The function longestUnivaluePath initiates the recursion:

  • It starts by calling calculate with the root node of the tree and an initial prevVal of -1 to handle the root appropriately.
  • Assuming no node values are negative allows differentiation between genuine node values and the initial condition.
  • Finally, it returns the value stored in longestPathResult, which would be the length of the longest univalue path.

This efficiently computes the longest univalue path by leveraging post-order traversal, ensuring each node and its descendants are completely processed before the node itself, thereby facilitating the update of path lengths correctly for the entire tree.

class Solution {
    int maxPath;

    int longestPath(TreeNode node, int val) {
        if (node == null) {
            return 0;
        }

        int leftPath = longestPath(node.left, node.val);
        int rightPath = longestPath(node.right, node.val);

        maxPath = Math.max(maxPath, leftPath + rightPath);

        if (node.val == val) {
            return Math.max(leftPath, rightPath) + 1;
        } else {
            return 0;
        }
    }

    public int longestUnivaluePath(TreeNode root) {
        longestPath(root, -1);
        return maxPath;
    }
}

The provided Java solution is designed to find the longest univalue path in a binary tree, where a univalue path is defined as a path in which all nodes have the same value. The solution uses a recursive helper method to track the longest path and updates a class variable maxPath to store the maximum length encountered during the traversal.

Here’s a breakdown of how the solution works:

• A TreeNode class is assumed to be defined elsewhere with attributes for the node value val, and pointers to left and right child nodes left and right.

• The main method longestUnivaluePath initializes the traversal by calling the helper method longestPath with the root of the tree and an arbitrary initial value.

• The recursive method longestPath:

  • Checks if the current node is null. If so, it returns a path length of zero since there is no node to process.
  • Recursively computes the longest paths in the left and right subtrees where the subtree roots must match the value of the current node. This ensures that the paths consist of nodes with the same value.
  • Updates maxPath using the longest paths returned from the left and right subtrees. This is crucial as it tracks the current maximum univalue path encountered in the tree.
  • Returns the length of the longest path continuing from the current node, but only if the current node's value matches the target value (val). This allows connecting the paths from the child to the parent if they are part of the same univalue path.
  • If values don't match, it returns zero which essentially ends the path at that node.

• After the recursive calls complete, maxPath holds the length of the longest univalue path found, and this value is returned by the longestUnivaluePath method.

In summary, this solution efficiently determines the longest univalue path in a binary tree using recursion to explore possible paths, and a max variable to keep track of the longest found so far, ensuring a comprehensive evaluation of all potential paths in the tree.