Tree Maximum Path Sum - first writing in July 5, 2015 - from the blog: http://juliachencoding.blogspot.ca/2015/07/itint5-tree-maximum-path-sum.html

TreeMaximumPathSum1.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);
        }

        /*
          July 6, 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中Binary Tree Maximum Path Sum的扩展，这里是树，而非二叉树。
         code source from blog:
         https://github.com/AnnieKim/ITint5/blob/master/013_%E6%A0%91%E4%B8%AD%E6%9C%80%E5%A4%A7%E8%B7%AF%E5%BE%84%E5%92%8C.cpp
        */

        public static int maxTreePathSumRe(TreeNode root, ref int res)
        {
            if (root == null) return res;

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

            // 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 
            // yeah, through the debug, she knows the idea. 
            int first = 0, second = 0;

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

                int sum = maxTreePathSumRe(b, ref res);
                if (sum > first)
                {
                    second = first;
                    first = sum;
                }
                else if (sum > second)
                {
                    second = sum;
                }
            }

            int maximum = root.val;
            maximum = max(maximum, root.val + first);
            res = max(res, maximum);
            res = max(res, root.val + first + second);
            return maximum;
        }

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

            maxTreePathSumRe(root, ref res);

            return res;
        }

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

August 4, 2016
The code from line 119 - 123 is not so readable.
Please make a few of corrections:

1. first, the input argument res - variable name - not accurate - res should be maxValueCrossRoot
2. function name: maxTreePathSumRe is confusing, will be better called "maxTreePathSumEndByRoot"
3. line 121, 122 can be merged into one line statement - easy to read
4. add some design spec for the function - maxTreePathSumRe