
public class LongestUnivaluePath {
	public int longestUnivaluePath(TreeNode root) {
        if(root == null) return 0;
        int[] count = new int[]{Integer.MIN_VALUE};
        helper(root, count);
        return count[0];
    }
    
    private int helper(TreeNode curr, int[] count){
    	// the reason of running recursion here instead of in later if condition is that
    	// no matter curr.val equals to the value of its left or right leaf, recusion should continus, then we decide the value
    	int left = curr.left != null ? helper(curr.left, count) : 0; 
        int right = curr.right != null ? helper(curr.right, count) : 0;
        int resLeft = curr.left != null && curr.val == curr.left.val ? left + 1 : 0;
        int resRight = curr.right != null && curr.val == curr.right.val ? right + 1 : 0;
        count[0] = Math.max(count[0], resLeft + resRight);
        return Math.max(resLeft, resRight);
    }
}
