n****r
发帖数: 120 | 1 Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
这道题咋解呢？每个节点DFS？ | b*****u
发帖数: 648 | 2 递归，有点tricky的地方在于递归函数每次返回的是最大的单侧路径，但同时把两侧加
自己的和与记录的最大值比较，最终返回的是那个记录值
class Solution {
public:
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int maxSoFar= root->val;
int tmp = maxContainRoot(root, maxSoFar);
return maxSoFar;
}
int maxContainRoot(TreeNode *root, int& maxSoFar)
{
if (root == NULL) return 0;
int leftMax = maxContainRoot(root->left,maxSoFar);
int rightMax = maxContainRoot(root->right,maxSoFar);
int result = root->val;
int maxPath = root->val;
int longerLeg = max(leftMax,rightMax);
result = max(result, result+longerLeg);
maxPath = max(maxPath,maxPath+leftMax);
maxPath = max(maxPath,maxPath+rightMax);
maxSoFar = max(maxSoFar, maxPath);
return result;
}
}; | n****r
发帖数: 120 | | m*****k
发帖数: 731 | 4 >if (root == NULL) return 0;
this won't work when node value is negative,
and I believe you considered negative,
from this line result = max(result, result+longerLeg);
May I ask why need maxPath? isn't 'result' enough?
and no need to calc result+longerLeg, just check if longerLeg > 0 , | b***m
发帖数: 5987 | |
|
