//Recursive solution: use a seperate recursive func to count the path begin with certain root
//Time: O(n), 12ms
//Space: O(h)
class Solution {
    int max = 0;//The longest univalue path length so far
    public int longestUnivaluePath(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 0;
        int ans = 0;//The longest path length that go through root
        longestUnivaluePath(root.left);
        longestUnivaluePath(root.right);
        if(root.left != null && root.val == root.left.val) {
            ans += 1 + pathBegin(root.left);
        }
        if(root.right != null && root.val == root.right.val) {
            ans += 1 + pathBegin(root.right);
        }
        //The longest path may go through root or may not
        max = Math.max(max, ans);
        //Return the longest univalue path after we traverse the whole tree
        return max;
    }

    //Return the path length begin with root
    private int pathBegin(TreeNode root) {
        if(root.left == null && root.right == null) return 0;
        int left = 0, right = 0;
        if(root.left != null && root.val == root.left.val) {
            left += 1 + pathBegin(root.left);
        }
        if(root.right != null && root.val == root.right.val) {
            right += 1 + pathBegin(root.right);
        }
        return Math.max(left, right);
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */