2014
11-19

# LeetCode-Binary Tree Maximum Path Sum[二叉树]

### Binary Tree Maximum Path Sum

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.

// LeetCode, Binary Tree Maximum Path Sum
// 时间复杂度O(n)，空间复杂度O(logn)
class Solution {
public:
int maxPathSum(TreeNode *root) {
max_sum = INT_MIN;
dfs(root);
return max_sum;
}
private:
int max_sum;
int dfs(const TreeNode *root) {
if (root == nullptr) return 0;
int l = dfs(root->left);
int r = dfs(root->right);
int sum = root->val;
if (l > 0) sum += l;
if (r > 0) sum += r;
max_sum = max(max_sum, sum);
return max(r, l) > 0 ? max(r, l) + root->val : root->val;
}
};


Maximum Subarray

1. 曾经见过一个捡垃圾的脚蹬三轮把一出租车给刮了，一直在那道歉。出租车司机快气死了，一捡垃圾的老头最值钱的就是那个破三轮了吧。

2. bottes vernies blanches

I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

3. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

4. 网站做得很好看，内容也多，全。前段时间在博客园里看到有人说：网页的好坏看字体。觉得微软雅黑的字体很好看，然后现在这个网站也用的这个字体！nice!

5. 您没有考虑 树的根节点是负数的情况， 若树的根节点是个很大的负数，那么就要考虑过不过另外一边子树了

6. int half(int *array,int len,int key)
{
int l=0,r=len;
while(l<r)
{
int m=(l+r)>>1;
if(key>array )l=m+1;
else if(key<array )r=m;
else return m;
}
return -1;
}
这种就能避免一些Bug
l,m,r
左边是l,m;右边就是m+1,r;