本文共 603 字，大约阅读时间需要 2 分钟。

题目：

解答：

自底向上求解。left_max right_max分别返回了左右子树的最大路径和，如果左右子树最大路径和小于0，那么返回零， 用这个最大路径和和根节点的值相加，来更新最大值，同时， 更新返回该树的最大路径值。

代码：

class Solution { public:	 int max = INT_MIN;	 int maxPathSum(TreeNode *root) {		 if (root == NULL)			 return 0;		 search(root);		 return max;	 }	 int search(TreeNode *root)	 {		 if (root == NULL)			 return 0;		 int left_max = search(root->left);		 int right_max = search(root->right);		 int sum = left_max + right_max + root->val;		 if (sum > max)			 max = sum;		 sum = left_max > right_max ? left_max + root->val : right_max + root->val;		 if (sum > 0)			 return sum;		 return 0;	 } };

转载地址：http://rutsi.baihongyu.com/