Leetcode之算法专题《Binary Tree Maximum Path Sum》
题目内容如下(链接:https://leetcode.com/problems/binary-tree-maximum-path-sum/description/)
首先说明本人代码运行速度打败了99%的人,见下图
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 {
public:
int dfs(TreeNode* root, int& ans){
if(!root)
{
return 0;
}
int leftSum = dfs(root->left, ans);
int rightSum = dfs(root->right, ans);
if(leftSum >= 0 && rightSum >= 0)
{
ans = max(ans, root->val + leftSum + rightSum);
}
int ret_val = root->val + max(max(leftSum, rightSum), 0);
ans = max(ans, ret_val);
return ret_val;
}
int maxPathSum(TreeNode* root) {
if(!root)
{
return 0;
}
int ans = root->val;
dfs(root, ans);
return ans;
}
};