```
class Solution {
public:
int dfs(int &result, TreeNode* root) {
if (!root) return 0;
int left_max = max(dfs(result, root->left), 0);
int right_max = max(dfs(result, root->right), 0);
result = max(result, left_max + right_max + root->val);
return max(max(left_max, right_max) + root->val, 0);
}
int maxPathSum(TreeNode* root) {
int result = INT_MIN;
dfs(result, root);
return result;
}
};
```