#Leetcode 687

class Triple {
    public int val;
    public int len;
    public int maxLen;
    public Triple(int val, int len, int maxLen) {
        this.val = val;
        this.len = len;
        this.maxLen = maxLen;
    }
}

class Solution {
    public int longestUnivaluePath(TreeNode root) {
        Triple res = findLongest(root);
        return res.maxLen;
    }
    
    private Triple findLongest(TreeNode node) {
        if (node == null) {
            return new Triple(1001, 0, 0);
        }
        
        Triple leftRes = findLongest(node.left);
        Triple rightRes = findLongest(node.right);
        int oneEndLen = 0, twoEndLen = 0;
        if (leftRes.val == node.val && rightRes.val == node.val) {
            twoEndLen = leftRes.len + rightRes.len + 2;
            oneEndLen = Math.max(leftRes.len, rightRes.len) + 1;
        } else if (leftRes.val == node.val) {
            oneEndLen = leftRes.len + 1;
        } else if (rightRes.val == node.val) {
            oneEndLen = rightRes.len + 1;
        }
        int maxLen = Math.max(Math.max(leftRes.maxLen, rightRes.maxLen), Math.max(oneEndLen, twoEndLen));
        return new Triple(node.val, oneEndLen, maxLen);
    }
}