Monday, July 6, 2015

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,相应的路径为56之间的路径。
扩展:此题算法也可用来解决另一个非常常见的面试题树的直径(求树中任意两结点路径的长度的最大值)。
可以认为树中每个结点的val值为1,那么求最长路径相当于求路径值最大的路径。
Solution: LeetCodeBinary 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


No comments:

Post a Comment