Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Example 1:
Input: [1,2,3]
1
/ \
2 3
Output: 6 Example 2:
Input: [-10,9,20,null,null,15,7]
-10
/
9 20
/
15 7
Output: 42
// 32ms, 84%
/**
* 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 {
private:
int maxPathSum2(TreeNode* root, int& maxV) {
if (!root) return 0;
int l = max(0, maxPathSum2(root->left, maxV));
int r = max(0, maxPathSum2(root->right, maxV));
maxV = max(maxV, l + r + root->val);
return max(l, r) + root->val;
}
public:
int maxPathSum(TreeNode* root) {
auto res = INT_MIN;
maxPathSum2(root, res);
return res;
}
};
// 36ms, 75%
/**
* 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 {
private:
pair<int,int> maxPathSum2(TreeNode* root) {
if (!root) return {0, INT_MIN};
auto lsum = maxPathSum2(root->left);
auto rsum = maxPathSum2(root->right);
auto res1 = max(root->val, max(lsum.first, rsum.first) + root->val);
auto res2 = root->val;
if (lsum.first > 0) res2 += lsum.first;
if (rsum.first > 0) res2 += rsum.first;
res2 = max(res2, max(lsum.second, rsum.second));
return {res1, res2};
}
public:
int maxPathSum(TreeNode* root) {
auto r = maxPathSum2(root);
return max(r.first, r.second);
}
};