Maximum Path Sum in the tree - second writing - make the code more readable, work on maximum path sum end by root, then, add max value cross root.

MaximumPathSumTreeBetter.cs

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

namespace TreeMaximumPathSum
{
    class TreeNode
    {
        public int val;
        public TreeNode[] children;

        public TreeNode(int x)
        {
            val = x;
            children = null;
        }
    };

    class Program
    {
        static void Main(string[] args)
        {
            /*
             * Test case: 
             * 
                    -10
                  /  |  \
                 2   3   4
                    / \
                   5  -1
                      /
                     6
                    /
                   -1
             * Maximum path sum: 5-> 3-> -1-> 6 , result is 13
             */
            TreeNode n1 = new TreeNode(-10);
            n1.children = new TreeNode[3];

            n1.children[0] = new TreeNode(2);
            n1.children[1] = new TreeNode(3);
            n1.children[2] = new TreeNode(4);

            TreeNode l2 = n1.children[1];
            l2.children = new TreeNode[2];
            l2.children[0] = new TreeNode(5);
            l2.children[1] = new TreeNode(-1);

            TreeNode l3 = l2.children[1];
            l3.children = new TreeNode[1];
            l3.children[0] = new TreeNode(6);
            l3.children[0].children = new TreeNode[1];
            l3.children[0].children[0] = new TreeNode(-1);

            int result = maxTreePathSum(n1);
        }

        /*
          Augst 4, 2016
         * 
         题目: 树中最大路径和
         难度: Easy
         链接: http://www.itint5.com/oj/#13
         问题: 
         给定一棵树的根结点，树中每个结点都包含一个整数值val。
         我们知道树中任意2个结点之间都存在唯一的一条路径，路径值为路径上所有结点值之和。
         请计算最大的路径值（允许路径为空）。
         样例：
            -10
          /  |  \
         2   3   4
            / \
           5  -1
              /
             6
            /
           -1
         最大的路径值为13，相应的路径为5到6之间的路径。
         扩展：此题算法也可用来解决另一个非常常见的面试题“树的直径”（求树中任意两结点路径的长度的最大值）。
         可以认为树中每个结点的val值为1，那么求最长路径相当于求路径值最大的路径。
         Solution: LeetCode 124 中Binary Tree Maximum Path Sum的扩展，这里是树，而非二叉树。
         
         * julia added comment: need to find maximum path through the root node, 
           so, multiple children, only keep first two most biggest pathes. 
           For the test case, root.val = -10, there are 3 children, each has maximum path length through the root node: 2, 8, 4
           so, the consideration is first 2 largest path length, 8 and 4. 
           -10 + 8 +4                     
        */

        public static int maxSumEndByRoot(TreeNode root, ref int maxSumCrossRoot)
        {
            if (root == null) return maxSumCrossRoot;

            int N = (root.children == null) ? 0 : root.children.Length;

            int[] top2 = new int[2]; 

            for (int i = 0; i < N; ++i)
            {
                TreeNode[] arr = root.children;
                TreeNode runner = (TreeNode)arr[i];

                int sum = maxSumEndByRoot(runner, ref maxSumCrossRoot);                 
                
                if (sum > top2[0])
                {
                    top2[1] = top2[0];
                    top2[0] = sum;
                }
                else if (sum > top2[1]) 
                {
                    top2[1] = sum;
                }
            }

            int rVal = root.val;
            int[] sumArr = { rVal, rVal + top2[0], rVal + top2.Sum()}; 

            maxSumCrossRoot = max(maxSumCrossRoot, ArrayMaximum(sumArr)); 
            
            return max(sumArr[0], sumArr[1]);
        }

        public static int maxTreePathSum(TreeNode root)
        {
            int res = 0;

            maxSumEndByRoot(root, ref res);

            return res;
        }

        /*
         * The maximum value in the array 
         */
        public static int ArrayMaximum(int[] arr)
        {
            if(arr == null || arr.Length == 0)
                return 0; 

            int max = 0; 
            for(int i=0; i< arr.Length; i++)
            {
                max = (arr[i] > max) ? arr[i] : max; 
            }

            return max; 
        }

        public static int max(int a, int b)
        {
            return Math.Max(a, b);
        }
    }
}