题解 | #二叉树的最大路径和#

class Solution {
public:
/**
*
* @param root TreeNode类
* @return int整型
*/
int maxPathSum(TreeNode *root) {
// write code here
// 后序遍历，记录左右子树最大的路径节点和
// 因为需要分别记录左子树和右子树的最大路径和，用循环实现起来比较麻烦
postOrder(root);
return maxSum;
}
int postOrder(TreeNode *root) {
if (!root) return 0;
int left = postOrder(root->left);
int right = postOrder(root->right);
int current = root->val;
if (left > 0) current += left;
if (right > 0) current += right;
maxSum = max(maxSum, current);
// 注意：此处返回的是max(左+中，右+中, 中)，左+右+中不满足题意
return max(root->val, max(left, right) + root->val);
}
private:
int maxSum = INT_MIN;
};