Leetcode 124 - Binary Tree Maximum Path Sum - add more comment, analysis and reasoning.

Leetcode124_BTreeMaximumPathSum_P1_MoreComment.cs

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
         * 
         * Add some analysis and reasoning here:  
         * The problem is to solve the path from any node of the tree to another node of the tree. 
         * We should simplify the case: 
         * 1. Single path from root node to any node in the tree
         * 2. Single path from any node to the root node and then to another node in the tree
         * 
         * Since we are doing recursive calls, so any node can be a root node in a subtree, and 
         * the above 2 cases, second case 2 actually is easily calculated based on test case 1:
         *   declare variable called maxValueCrossRoot, 
         *   maxValueCrossRoot = root.val; 
         *   if(left child's test case 1 result > 0) 
         *      maxValueCrossRoot += valueLeft; 
         *   if(right child's test case 1 result > 0)
         *      maxValueCrossRoot + = valueRight; 
         *      
         * Another concern is to make the function recursive, so it is easy to solve. Root node 
         * is the key to the recursive function design. 
         * 
         * 
         * 
         */
        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;

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