递归
- 思路：
- 定义节点最大贡献值：
- 空节点最大贡献值是 0；
- 叶子结点最大贡献值是其本身；
- 非叶子节点最大贡献值是其节点值与其子节点贡献值中最大的值的和；
- 节点最大路径和为：
- 当前节点值 + 左子节点最大贡献和 + 右子节点最大贡献和，该值如果超过之前最大路径和则更新，否则为之前值；
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxPathSum(TreeNode* root) {
maxGain(root);
return maxSum;
}
private:
int maxGain(TreeNode* node) {
if (nullptr == node) {
return 0;
}
int leftGain = std::max(maxGain(node->left), 0);
int rightGain = std::max(maxGain(node->right), 0);
int nodeGain = node->val + leftGain + rightGain;
maxSum = std::max(maxSum, nodeGain);
return node->val + std::max(leftGain, rightGain);
}
private:
int maxSum = INT_MIN;
};