ITINT5: tree maximum path sum (I)

July 6, 2015

Problem statement:

链接: 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的扩展，这里是树，而非二叉树。

Share C# code:

https://github.com/jianminchen/TreeMaxPathSum/blob/master/Program.cs

February 3, 2016

work on Leetcode question 124: Binary Tree Maximum Path Sum