Saturday, July 4, 2015

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, 
 
 /  \ 
2   3 
Return 6.

Blogs to read:




原来这讲解很清楚:


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


Julia's C# practice.



Extension problem:


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):
计算树的最长path2种情况:
1. 过根的path.
  (1)如果左子树从左树根到任何一个Nodepath大于零,可以链到root
  (2)如果右子树从右树根到任何一个Nodepath大于零,可以链到root
2. 不通过根的path. 这个可以取左子树及右子树的path的最大
所以创建一个inner class:
记录2
1. 树的最大path
2. 树从根节点出发到任何一个节点的最大path.
注意,当root == null,以上2值都要置为Integer_MIN_VALUE; 为没有节点可取的时候,是不存在solution的。以免干扰递归的计

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:

No comments:

Post a Comment