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

Leetcode 124: Maximum binary tree path sum

July  4, 2015

Problem statement:

Given a binary tree, find the maximum path sum. 

The path may start and end at any node in the tree. 

For example: 

Given the below binary tree, 

  1 

 /  \ 

2   3 

Return 6.

Blogs to read:

http://blog.unieagle.net/2012/12/09/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Abinary-tree-maximum-path-sum/

http://shanjiaxin.blogspot.ca/2014/02/binary-tree-maximum-path-sum-leetcode.html

http://bangbingsyb.blogspot.ca/2014/11/leetcode-binary-tree-maximum-path-sum.html

http://jane4532.blogspot.ca/2013/09/binary-tree-maximum-path-sumleetcode.html

原来这讲解很清楚:

http://www.cnblogs.com/yuzhangcmu/p/4172855.html

The best readable code, and perfect to follow for this problem:

https://github.com/xiaoxq/leetcode-cpp/blob/master/src/BinaryTreeMaximumPathSum.cpp

Julia's C# practice.

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

https://github.com/jianminchen/Leetcode_C-/blob/master/124BinaryTreeMaximumPathSum.cs

Extension problem:

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

February 3, 2016

Review the algorithm, need to figure out how to make this algorithm easy to remember, recall, write without a bug.

Good analysis from the blog (http://www.cnblogs.com/yuzhangcmu/p/4172855.html):

计算树的最长path有2种情况：

1. 通过根的path.

  (1)如果左子树从左树根到任何一个Node的path大于零，可以链到root上

  (2)如果右子树从右树根到任何一个Node的path大于零，可以链到root上

2. 不通过根的path. 这个可以取左子树及右子树的path的最大值。

所以创建一个inner class:

记录2个值：

1. 本树的最大path。

2. 本树从根节点出发到任何一个节点的最大path.

注意，当root == null,以上2个值都要置为Integer_MIN_VALUE; 因为没有节点可取的时候，是不存在solution的。以免干扰递归的计算

http://www.cnblogs.com/yuzhangcmu/p/4172855.html

Practice using this class as return type:

private class ResultType { int singlePath; int maxPath; ResultType(int singlePath, int maxPath) { this.singlePath = singlePath; this.maxPath = maxPath; } Read more blogs: http://buttercola.blogspot.ca/2014/08/leetcode-binary-tree-maximum-path-sum.html Discussion of global variable - max value - Julia likes the discussion  https://leetcode.com/discuss/14190/accepted-short-solution-in-java