i******t
发帖数: 22541 | 1 这个题目中
假设当前 p
那么最大值可以 为
p->val
p->val + p->left->val
p->val + p->right->val
p->val + p->right->val+ p->left->val
这四种情况
但是为什么不能是单独的
p->left->val
或者
p->right->val
呢？
如果 p->val 本身是负数 ，左子树 最大值 是正 数 那么最大值不应该算上 p本身吧
》？
求解惑
thx | T*******e
发帖数: 4928 | 2 所以你会用一个变量存着p的子树的最大和值maxSoFar，然后比较p的子树的最大值
maxSoFar与那四个通过p的最大和值maxAcrossCurNode,来更新从下往上走到p为止的最
大值maxSoFar。
int maxPathSumHelper(TreeNode *cur, int &maxSoFar){
if(!cur) return 0;
int maxLeft=maxPathSumHelper(cur->left, maxSoFar);
int maxRight=maxPathSumHelper(cur->right, maxSoFar);
int maxAcrossCurNode=cur->val;
if(maxLeft>0) maxAcrossCurNode+=maxLeft;
if(maxRight>0) maxAcrossCurNode+=maxRight;
maxSoFar=max(maxAcrossCurNode, maxSoFar); //update maxSoFar !!!!
return max(cur->val, cur->val+ max(maxLeft, maxRight));
}
int maxPathSum(TreeNode *root){
if(!root) return INT_MIN;
int maxSoFar=root->val;
maxPathSumHelper(root, maxSoFar);
return maxSoFar;
} | l*******0
发帖数: 63 | 3 if(maxLeft>0) cur+=maxLeft;
if(maxRight>0) cur+=maxRight;
处的cur应改为maxAcrossCurNode？
【在 T*******e 的大作中提到】
: 所以你会用一个变量存着p的子树的最大和值maxSoFar，然后比较p的子树的最大值
: maxSoFar与那四个通过p的最大和值maxAcrossCurNode,来更新从下往上走到p为止的最
: 大值maxSoFar。
: int maxPathSumHelper(TreeNode *cur, int &maxSoFar){
: if(!cur) return 0;
: int maxLeft=maxPathSumHelper(cur->left, maxSoFar);
: int maxRight=maxPathSumHelper(cur->right, maxSoFar);
: int maxAcrossCurNode=cur->val;
: if(maxLeft>0) maxAcrossCurNode+=maxLeft;
: if(maxRight>0) maxAcrossCurNode+=maxRight;
| T*******e
发帖数: 4928 | 4 yeah. typo. Thank you for pointing that out. Bug free is really difficult.
【在 l*******0 的大作中提到】
: if(maxLeft>0) cur+=maxLeft;
: if(maxRight>0) cur+=maxRight;
: 处的cur应改为maxAcrossCurNode？
|
|
