幼儿园骨折求问 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Parenting - 为人父母

幼儿园骨折求问

幼儿园骨折求问# Parenting - 为人父母

i*t2014-11-05 08:11

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

l*n2014-11-05 08:11

2 楼

幼儿园从台子上跳下来，胳膊骨折，进ER，动手术
请问幼儿园有责任么，估计得几千的bill，幼儿园会cover一部分么，谢谢

T*e2014-11-05 08:11

3 楼

所以你会用一个变量存着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;
}

R*i2014-11-05 08:11

4 楼

幼儿园应该买了保险。具体他们付多少钱得问幼儿园...

l*02014-11-05 08:11

5 楼

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;