using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _687_longest_univalue_path_II
{
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }

    class Program
    {
        static void Main(string[] args)
        {
        }

        /// <summary>
        /// Jan. 19, 2019
        /// The design has a problem
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public static int LongestUnivaluePath(TreeNode root) {
            if (root == null || (root.left == null && root.right == null))
                return 0;

            if (root.left != null && root.val == root.left.val && root.right != null && root.val == root.right.val)
            {
                return 2 + LongestUnivaluePath(root.left) + LongestUnivaluePath(root.right);
            }

            var left = LongestUnivaluePath(root.left);
            var right = LongestUnivaluePath(root.right);

            if(root.left != null && root.val == root.left.val)
            {
                left++;
            }

            if(root.right != null && root.val == root.right.val)
            {
                right++;
            }

            return Math.Max(left, right);
        }
    }
}