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