1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     int maxPathSum(TreeNode* root) {13         int partialSum=0;14         int maxSum=INT_MIN;15         calculateSum(root, partialSum, maxSum);16         return maxSum;17     }18 19     //partialSum means the maximal sum which contains only current node and only one of its subtree (either left or right)20     void calculateSum(TreeNode * root, int & partialSum, int & maxSum) {21         if(root == NULL) return;22         int leftPartialSum=0;23         if(root->left != NULL)24             calculateSum(root->left, leftPartialSum, maxSum);25 26         int rightPartialSum=0;27         if(root->right != NULL)28             calculateSum(root->right, rightPartialSum, maxSum);29 30         partialSum=max(root->val, max(root->val+leftPartialSum, root->val+rightPartialSum));31         maxSum=max(partialSum, max(maxSum, leftPartialSum+rightPartialSum+root->val));32     }33 };

partialSum仅有如下几种情况：root, root+leftSubtree, root+rightSubtree. 即一条合法的路径。

maxSum有如下几种情况：1、即partialSum 2、左儿子+root+右儿子 3、之前的maxSum值

关于其中第三种情况的解释：maxSum存储了目前为止最大和路径的值,

                                     比如  -1

                                            /    \

                                          -2      3

                                     maxSum先是-2（处理-2节点时），然后是3（处理3时），最后是3（处理-1时）。而处理-1时partialSum为-1,-3,2中最大的，即2.

 

待重写以加深印象，留坑。

注意：                                         

int maxSum = INT_MIN;或int maxSum = 0x80000000

                 

 

另一种写法：

1 class Solution { 2 public: 3 int res; 4 int maxPathSum(TreeNode* root) { 5     res = 0x80000000; 6     dfs(root); 7     return res; 8 } 9 int dfs(TreeNode* tree){10     if(!tree) return 0;11     int left = dfs(tree->left), right = dfs(tree->right), tmp;12     tmp = max(tree->val, tree->val+left);13     tmp = max(tmp, tree->val+right);14     res = max(tmp, res);15     res = max(res, tree->val+left+right);16     return tmp;17 18 }19 };

 

顺便两份一模一样的代码居然跑的时间不一样，留坑。