c++
class Solution {
public:
int dfs(TreeNode* node, int& ans)
{
//返回以某个点为顶点深度权重和最大值
if(!node) return 0;
int d1 = dfs(node->left, ans);
int d2 = dfs(node->right, ans);
ans = max(ans, node->val + d1 + d2);
return max(0, node->val + max(d1, d2));
}
int maxPathSum(TreeNode* root) {
int ans = INT_MIN;
dfs(root, ans);
return ans;
}
};
c++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxPathSum(TreeNode* root) {
int res = INT_MIN;
dfs(root, res);
return res;
}
// 返回通过根节点的最大值
int dfs(TreeNode* root, int &res) {
if (!root) return 0;
int d1 = max(0, dfs(root->left, res));
int d2 = max(0, dfs(root->right, res));
//res 返回全局的最大值
res = max(d1+root->val+d2, res);
return root->val + max(d1, d2);
}
};
python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.res = float('-inf')
self.dfs(root)
return self.res
def dfs(self, root):
if root is None: return 0
left = max(0, self.dfs(root.left))
right = max(0, self.dfs(root.right))
self.res = max(left+root.val+right, self.res)
return root.val+max(left, right)