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

namespace _124BinaryTreeMaximumPathSum_JuliaWriteByHerself
{
    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)
        {
            int result = testCase_1();
            int result2 = testCase_2();
            int result3 = testCase_3();
        }

        /*
         * maximum value is ended by root value
         */
        public static int testCase_1()
        {
            TreeNode n1 = new TreeNode(3);
            n1.left = new TreeNode(2);
            n1.left.left = new TreeNode(1);
            n1.left.right = new TreeNode(3);

            n1.right = new TreeNode(-1);
            n1.right.left = new TreeNode(-2);
            n1.right.right = new TreeNode(-2);

            return maximumPathSum(n1);
        }

        /*
         * maximum value is in subtree somewhere
         */
        public static int testCase_2()
        {
            TreeNode n1 = new TreeNode(-3);
            n1.left = new TreeNode(2);
            n1.left.left = new TreeNode(1);
            n1.left.right = new TreeNode(3);

            n1.right = new TreeNode(-1);
            n1.right.left = new TreeNode(-2);
            n1.right.right = new TreeNode(-2);

            return maximumPathSum(n1);
        }

        /*
         *  Test case:
         *  9 6 -3 null null -6 2 null null -6 2 null null 2 null -6 -6 null null null null
         *
         * Maximum path is 6 9 -3 2 2
         */
        public static int testCase_3()
        {
            TreeNode n1 = new TreeNode(9);
            n1.left = new TreeNode(6);

            n1.right = new TreeNode(-3);
            n1.right.left = new TreeNode(-6);
            n1.right.right = new TreeNode(2);
            n1.right.right.left = new TreeNode(2);
            n1.right.right.left.left = new TreeNode(-6);
            n1.right.right.left.right = new TreeNode(-6);

            return maximumPathSum(n1);
        }
        /*
         * pass online judge
         *
         *
         */
        public static int maximumPathSum(TreeNode root)
        {
            if (root == null)
                return 0;

            int maxCrossRoot = Int32.MinValue;
            int maxEndRoot = getMaximumEndByRoot(root, ref maxCrossRoot);

            return   Math.Max(maxEndRoot, maxCrossRoot);
        }

        /*
         * Analyze the binary tree maximum path sum problem.
         *
         * Maximum path -
         * Can be analyzed by two variable
         * - Maximum value ended by root node
         * - Maximum value cross by root node
         *
         */
        private static int getMaximumEndByRoot(TreeNode root, ref int maxCrossRoot)
        {
            if (root == null)
                return 0;

            int left = getMaximumEndByRoot(root.left, ref maxCrossRoot);
            int right = getMaximumEndByRoot(root.right, ref maxCrossRoot);

            int value = root.val;
            if (left > 0)
                value += left;
            if (right > 0)
                value += right;

            maxCrossRoot = value > maxCrossRoot ? value : maxCrossRoot;

            int maxValue = Math.Max(root.val + left, root.val + right);
            return Math.Max(root.val, maxValue);     // 3 values, get maximum one.
        }
    }
}