【hard】124. Binary Tree Maximum Path Sum
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
/**
* 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 solution(TreeNode* root, int& best){ // my own solution
if (!root) return 0;
int left_sum = root->val + solution(root->left, best);
int right_sum = root->val + solution(root->right, best);
int curve_sum = left_sum + right_sum - root->val;
best = max({best, left_sum, right_sum, curve_sum, root->val});
return max({left_sum, right_sum, root -> val});
}
public:
int maxPathSum(TreeNode* root) { // it is the original function
int best = INT_MIN;
int eval = solution(root, best);
return max(best, eval);
}
};
转载于//www.cnblogs.com/sherry-yang/p/11421704.html
还没有评论,来说两句吧...