过去只是人生经历，并不是人生负担

[问题描述]

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.

[解题思路]

类似于最大连续子序列

1 class Solution { 2 public: 3     int maxPathSum(TreeNode *root) { 4         max_sum = root->val; 5         tt(root); 6         return max_sum; 7     } 8     int tt(TreeNode *root){ 9         if (root == NULL)10             return 0;11         int sum = root->val;12         int l = tt(root->left);13         int r = tt(root->right);14         sum += max(l, 0);15         sum += max(r, 0);16         max_sum = max(max_sum, sum);17         return max(l, r) > 0?(root->val + max(l, r)):(root->val);18     }19 private:20     int max_sum;21 };