LeetCode: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.

分析：设f(p) 是以节点p作为路径端点的最大路径和，例如下面的树

f(2) = 2+5=7, f(3) = 3+6=9, f(1) = f(3)+1=10

即f(p) = max(p->val , p->val+f(p->left), p->val+f(p->right)), 特别的当p=NULL 时，f(p) = 0; 本文地址

有以上可知经过p节点的路径的最大和maxsum(p) = max(f(p), f(p->left)+f(p->right)+p->val), 即取p为端点和p为中间节点的路径的较大值

因此可以通过树的后序遍历求得每个节点的maxsum，选取最大的即为最终结果，代码如下：

 1 /**
 2  * Definition for binary tree
 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         // IMPORTANT: Please reset any member data you declared, as
14         // the same Solution instance will be reused for each test case.
15         if(root == NULL)return 0;
16         int res = INT_MIN;
17         postorderTrav(root, res);
18         return res;
19     }
20     int postorderTrav(TreeNode *root, int& res)
21     {//返回值：root作为端点的path的最大值
22         int left = 0, right = 0; 
23         if(root->left)left = postorderTrav(root->left, res);
24         if(root->right)right = postorderTrav(root->right, res);
25         int res_this = max(max(left+root->val, right+root->val), root->val);
26         int tmp = max(res_this, left + right + root->val);
27         if(tmp > res)
28             res = tmp;
29         return res_this;
30     }
31 };