blob: 7be19b288d0bf2980bbb0a7d62f54887e5e4446f (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include "leetcode.h"
class Solution {
public:
int sum;
int maxPathSum(TreeNode *root) {
sum = INT_MIN;
solve(root);
return sum;
}
private:
int solve(TreeNode *root) {
if (!root)
return 0;
int left = max(0, solve(root->left));
int right = max(0, solve(root->right));
sum = max(sum, left + right + root->val);
return max(left, right) + root->val;
}
};
|