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 res=INT_MIN; 14 help(root, res); 15 return res; 16 } 17 18 int help(TreeNode* root, int& res){ 19 if(root==NULL) 20 return -1; 21 int releft=max(0, help(root->left, res)); 22 int reright=max(0, help(root->right, res)); 23 res = max(res, root->val+releft+reright); 24 return root->val + max(releft, reright); 25 } 26 };
递归过程比较简单，但是要注意一个问题，对于每个节点，每次返回的是过该节点的最大单链。
全局最大路径在遍历时就更新，取值为max（当前节点能取到的最大值，上一次最大值）
还有一个要注意的就是在遍历左右孩子节点的最大路径返回时，要和0进行比较，因为如果遍历孩子节点返回的是负值，和当前节点累加后得到的值反而会变小。
所以用0进行比较，小于0直接舍弃。
当节点为空时，返回小于等于0的值均可，因为小于等于0的值返回后会被左右孩子返回值和0的比较函数被置为0.
下面这个代码要笨一些，但是思路特别清晰，完全自己想出来的
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 maxlen=0; 14 vector<int> res = help(root); 15 return res[1]; 16 } 17 18 vector<int> help(TreeNode* root){ 19 if(root==NULL){ 20 // {过该点最大单链，在该点的最大路径} 21 vector<int> re={0, INT_MIN}; 22 return re; 23 } 24 vector<int> releft=help(root->left); 25 vector<int> reright=help(root->right); 26 vector<int> res(2,0); 27 res[0] = max(releft[0], reright[0]) + root->val; 28 res[0] = max(res[0], root->val); 29 res[1] = max(res[0], max(releft[1], reright[1])); 30 res[1] = max(res[1], root->val); 31 res[1] = max(res[1], releft[0]+reright[0]+root->val); 32 return res; 33 } 34 };
124. Binary Tree Maximum Path Sum
原文：https://www.cnblogs.com/zhuangbijingdeboke/p/11686044.html