logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
贴个自己的答案：Binary Tree Max Path Sum
avatar
贴个自己的答案：Binary Tree Max Path Sum# JobHunting - 待字闺中
t*a
1 楼
经常看大家的故事,有感动的有气愤的有无聊的,也想和大家说一说我的看法.
和老公的关系是至关重要的,他才是那个要和你过一辈子的人,你的公公婆婆你的爸爸妈
妈,不管我们多么希望永远和他们在一起,但是老天爷不答应.自己的爸爸妈妈当然是至
爱的,老公即使不是至爱的,但他是要和你日夜陪伴,一生一世的.
所以无论遇到什么矛盾(和公婆或其他)我都不会把他逼到一个痛苦的境地,如果公婆做
了伤害我们的事我会无意地说出来,但我一看到他为难的表情,我就会给他台阶"哎,其实
也没什么,老人家我们也别和他们计较了",他反而会说"他们真的讨厌,我去说他们",我
当然不会让他去说他们,我老公心里有数就行了呗.反之你要是非要他和你一起说他爸妈
的闲话,逼急了他先把你干掉了,要知道,那是他爸妈! 有时候我也会叨唠叨唠我父母无
关紧要的缺点,让他知道父母也是可以被叨唠的.
包括归不归的事,他前几年吵着要回去,我知道拦不住他（人在兴头上都是栏不住的，不
是说就他栏不住）,就高高兴兴和他归了,回去后事业倒是没有想象中的那么风光有前途
,但我们把亚洲玩了个遍,他吃吃喝喝腻了就说我们回美国吧,我们又高高兴兴回美国了,
什么
avatar
a*x
2 楼
网上搜到的都没有考虑negative的情况，比如一个tree只有一个node，这个node的值
是negative。
下面是我自己的答案，已经pass OJ：
class LocalResult
{
int localMaxPathSum; // local max path sum
int localSubPathSum; // either root, or root+left, or root+right

public LocalResult(int maxPathSum, int subPathSum)
{
this.localMaxPathSum = maxPathSum;
this.localSubPathSum = subPathSum;
}
}
public class binaryTreeMaxPathSum {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
}
public int maxPathSum(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
LocalResult result = maxPathSumLocal(root);

return result.localMaxPathSum > result.localSubPathSum ? result.
localMaxPathSum : result.localSubPathSum;
}
private int maxOfThree(int a, int b, int c)
{
int result = a;
if(b > result)
result = b;
if(c > result)
result = c;
return result;
}

private LocalResult maxPathSumLocal(TreeNode root)
{
if(root == null)
{
return null;
}

LocalResult left = maxPathSumLocal(root.left);
LocalResult right = maxPathSumLocal(root.right);

int localMaxPathSum = root.val;
int localSubPathSum = root.val;

if(left != null && left.localSubPathSum > 0)
localMaxPathSum += left.localSubPathSum;

if(right != null && right.localSubPathSum > 0)
localMaxPathSum += right.localSubPathSum;

if(left != null && right != null)
{
localMaxPathSum = maxOfThree(localMaxPathSum, left.
localMaxPathSum, right.localMaxPathSum);
localSubPathSum = maxOfThree(root.val, root.val + left.
localSubPathSum, root.val + right.localSubPathSum);
}
else if(left != null)
{
localMaxPathSum = localMaxPathSum > left.localMaxPathSum ?
localMaxPathSum : left.localMaxPathSum;
localSubPathSum = localSubPathSum > root.val + left.
localSubPathSum ? localSubPathSum : root.val + left.localSubPathSum;
}
else if(right != null)
{
localMaxPathSum = localMaxPathSum > right.localMaxPathSum ?
localMaxPathSum : right.localMaxPathSum;
localSubPathSum = localSubPathSum > root.val + right.
localSubPathSum ? localSubPathSum : root.val + right.localSubPathSum;
}

return new LocalResult(localMaxPathSum, localSubPathSum);
}
}
觉得有些臃肿，主要是return null而不是0当碰到leave时，所以得判断返回的结果是
不是null。有更简洁的吗？
avatar
t*a
3 楼
怎么看不到

【在 t********a 的大作中提到】
: 经常看大家的故事,有感动的有气愤的有无聊的,也想和大家说一说我的看法.
: 和老公的关系是至关重要的,他才是那个要和你过一辈子的人,你的公公婆婆你的爸爸妈
: 妈,不管我们多么希望永远和他们在一起,但是老天爷不答应.自己的爸爸妈妈当然是至
: 爱的,老公即使不是至爱的,但他是要和你日夜陪伴,一生一世的.
: 所以无论遇到什么矛盾(和公婆或其他)我都不会把他逼到一个痛苦的境地,如果公婆做
: 了伤害我们的事我会无意地说出来,但我一看到他为难的表情,我就会给他台阶"哎,其实
: 也没什么,老人家我们也别和他们计较了",他反而会说"他们真的讨厌,我去说他们",我
: 当然不会让他去说他们,我老公心里有数就行了呗.反之你要是非要他和你一起说他爸妈
: 的闲话,逼急了他先把你干掉了,要知道,那是他爸妈! 有时候我也会叨唠叨唠我父母无
: 关紧要的缺点,让他知道父母也是可以被叨唠的.
avatar
h*n
4 楼
面试写成这样子就挂了
class Solution {
public:
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int res;
int g;

res = helper(root, g);
return res;
}

int helper(TreeNode * root, int & g)
{
if(!root)
{
g = 0;
return 0;
}

int leftG, rightG;
int maxSum = INT_MIN;

int leftMax = helper(root->left, leftG);
int rightMax = helper(root->right, rightG);
if(!root->left&&!root->right)
maxSum = root->val;
else if(!root->left)
maxSum = max(rightMax, root->val + leftG + rightG);
else if(!root->right)
maxSum = max(leftMax, root->val + leftG + rightG);
else maxSum = max(max(leftMax,rightMax),root->val + leftG + rightG);

g = max(0, root->val+max(leftG, rightG));
return maxSum;
}
};
avatar
g*9
5 楼
Re ->
你们觉得一个没遇过事的人是上面所
写的那样的吗?"曾经沧海,除却巫山",换一颗淡定的心
Not every one will have that luxury to 曾经沧海 and gain 一颗淡定的心

【在 t********a 的大作中提到】
: 经常看大家的故事,有感动的有气愤的有无聊的,也想和大家说一说我的看法.
: 和老公的关系是至关重要的,他才是那个要和你过一辈子的人,你的公公婆婆你的爸爸妈
: 妈,不管我们多么希望永远和他们在一起,但是老天爷不答应.自己的爸爸妈妈当然是至
: 爱的,老公即使不是至爱的,但他是要和你日夜陪伴,一生一世的.
: 所以无论遇到什么矛盾(和公婆或其他)我都不会把他逼到一个痛苦的境地,如果公婆做
: 了伤害我们的事我会无意地说出来,但我一看到他为难的表情,我就会给他台阶"哎,其实
: 也没什么,老人家我们也别和他们计较了",他反而会说"他们真的讨厌,我去说他们",我
: 当然不会让他去说他们,我老公心里有数就行了呗.反之你要是非要他和你一起说他爸妈
: 的闲话,逼急了他先把你干掉了,要知道,那是他爸妈! 有时候我也会叨唠叨唠我父母无
: 关紧要的缺点,让他知道父母也是可以被叨唠的.
avatar
f*7
6 楼
贴个我的，divide-and-conquer
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int globalMax = INT_MIN;
maxPathSum(root, globalMax);
return globalMax;
}

//return the max path sum INCLUDES root node
//which is the key to this elegant divide-and-conquer solution
int maxPathSum(TreeNode* root, int& globalMax)
{
if (NULL == root)
{
return 0;
}
else
{
//max sum of left leg
int leftSum = maxPathSum(root->left, globalMax);

//max sum of right leg
int rightSum = maxPathSum(root->right, globalMax);

//conquer stage
//max sum cross the root, 4 possibilities
int crossSum = max(root->val, max(leftSum + root->val, max(
rightSum + root->val, leftSum + root->val + rightSum)));

//update global variable if nec.
if (crossSum > globalMax)
{
globalMax = crossSum;
}

//return the max path sum INCLUDES root node
return max(root->val, max(root->val + leftSum, root->val +
rightSum));
}
}
};
avatar
x*a
7 楼
都说女人是拿来疼的,其实老公也是拿来疼和包容的
avatar
l*b
8 楼
int maxPathSum(Node *h) {
int m = h->val;
stack ss;
stack ms;
Node *ret = NULL;
while(h || !ss.empty()) {
if(h) {
ss.push(h);
h = h->l;
continue;
}
h = ss.top();
if(NULL == h->r || ret == h->r) {
int mr = 0, ml = 0;
if(h->r) { mr = max(ms.top(), 0); ms.pop();}
if(h->l) { ml = max(ms.top(), 0); ms.pop();}
m = max(m, h->val + mr + ml);
ms.push(h->val + max(mr, ml));
ret = h;
h = NULL;
ss.pop();
}
else
h = h->r;
}
return m;
}
后序遍历的写法
avatar
t*i
9 楼
说得很好！
夫妻两个人搭伴儿过日子嘛，就得相互体谅相互理解。
avatar
l*b
10 楼
int maxPathSII(Node *h) {
int m = h->val;
int res = helper(h, m);
return m;
}
int helper(Node *h, int &m) {
if(NULL == h) return 0;
int ml = max(helper(h->l, m), 0);
int mr = max(helper(h->r, m), 0);
m = max(m, h->val + mr + ml);
return h->val + max(mr, ml);
}
学习一下递归的写法。。
avatar
s*d
11 楼
人和人真的是不一样的，两个豁达明理的人不管怎么过基本上不会出什么大错的，但只
要有一个无事生非或不明是非的，那日子就没法过（当然有这样的人运气好没碰到大挫
折也过下来了），任性自私本来就是人的本性，碰到事儿了，这种本性一旦爆发出来，
就有可能没法收拾。所以说家家有本难念的经，不身在其中是没法理解的。只能说lz还
是运气好，有个与自己相知相合的人，可能自己的性格好也是关键，但假如你lg是个非
常差劲的人，你觉得自己还淡定得了吗？
avatar
a*x
12 楼
多谢指教，仿照你的写了个java的，pass了：
private LocalResult maxPathSumLocal(TreeNode root)
{
if(root == null)
{
return new LocalResult(0,0);
}

LocalResult left = maxPathSumLocal(root.left);
LocalResult right = maxPathSumLocal(root.right);

int maxSoFar,leg;

if(root.left == null && root.right == null)
maxSoFar = root.val;
else if(root.left == null)
maxSoFar = maxOfTwo(right.maxSoFar, root.val + right.leg);
else if(root.right == null)
maxSoFar = maxOfTwo(left.maxSoFar, root.val + left.leg);
else
maxSoFar = maxOfThree(left.maxSoFar, right.maxSoFar, root.val +
left.leg + right.leg);

leg = maxOfThree(0,root.val + left.leg, root.val + right.leg);

return new LocalResult(maxSoFar, leg);
}

【在 h****n 的大作中提到】
: 面试写成这样子就挂了
: class Solution {
: public:
: int maxPathSum(TreeNode *root) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: int res;
: int g;
:
: res = helper(root, g);
avatar
g*9
13 楼
hand hand
even though he or she 无事生非或不明是非, still trying to 淡定, then every
improvement becomes a surprise and encouragement.

【在 s******d 的大作中提到】
: 人和人真的是不一样的，两个豁达明理的人不管怎么过基本上不会出什么大错的，但只
: 要有一个无事生非或不明是非的，那日子就没法过（当然有这样的人运气好没碰到大挫
: 折也过下来了），任性自私本来就是人的本性，碰到事儿了，这种本性一旦爆发出来，
: 就有可能没法收拾。所以说家家有本难念的经，不身在其中是没法理解的。只能说lz还
: 是运气好，有个与自己相知相合的人，可能自己的性格好也是关键，但假如你lg是个非
: 常差劲的人，你觉得自己还淡定得了吗？
avatar
d*e
14 楼
好像大家都要一个global max，这个有什么用吗？我觉得不要也没关系。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
这里为什么要左右都加呢？这样不成为一条path吧。

【在 f*****7 的大作中提到】
: 贴个我的，divide-and-conquer
: /**
: * Definition for binary tree
: * struct TreeNode {
: * int val;
: * TreeNode *left;
: * TreeNode *right;
: * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
: * };
: */
avatar
s*d
15 楼
对啊，我们改变不了别人，但可以完善自己，如果努力了还是不行（对方的原因或是环
境的原因），那就不要拖泥带水了，当断则断

【在 g*****9 的大作中提到】
: hand hand
: even though he or she 无事生非或不明是非, still trying to 淡定, then every
: improvement becomes a surprise and encouragement.
avatar
P*r
16 楼
和我的几乎一点不差。不知道还能不能有跟好一些的。

【在 f*****7 的大作中提到】
: 贴个我的，divide-and-conquer
: /**
: * Definition for binary tree
: * struct TreeNode {
: * int val;
: * TreeNode *left;
: * TreeNode *right;
: * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
: * };
: */
avatar
m*n
17 楼
哦，问个逻辑问题
如果你们夫妻俩都觉得对方才是过一辈子的人，那你老公怎么会为了父母把你干掉阿？
好吧，我承认你们家庭关系挺好，但这真跟你的理论没啥关系
主要是你们俩都看得开
要是俩都看不开的，就算也觉得对方重要的不得了，肯定也不安宁
avatar
f*7
18 楼
这才是divide-and-conquer啊
一条path，可能全在左子树，可能全在右子树，也可能跨过root
跨过root的path，就有四种情况。
我这么写，每个子树的sum都是一条从子树的root开始的path，这样和root相连成一条
path。
你这么后序递归走几步，就发现leftSum和rightSum是root的“两条腿”

【在 d**e 的大作中提到】
: 好像大家都要一个global max，这个有什么用吗？我觉得不要也没关系。
:
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: 这里为什么要左右都加呢？这样不成为一条path吧。
avatar
q*e
19 楼
木错

【在 m********n 的大作中提到】
: 哦，问个逻辑问题
: 如果你们夫妻俩都觉得对方才是过一辈子的人，那你老公怎么会为了父母把你干掉阿？
: 好吧，我承认你们家庭关系挺好，但这真跟你的理论没啥关系
: 主要是你们俩都看得开
: 要是俩都看不开的，就算也觉得对方重要的不得了，肯定也不安宁
avatar
i*e
20 楼
20
/ \
-3 -5
/ \
3 8
/ \ \
-2 -1 10
/ /
6 -7
这个test case的max path sum 应该是20-> -3 -> 8 -> 10 (sum = 35).
按照你的程序
在根节点 20： maxSum = max(max(helper(-3, leftG), helpfer(-5， rightG)， 20
+ leftG + rightG);
因为leftG包含了以结点3为子树根节点的一条路径（6 -> -1 -> 3 -> -3 -> 8 -> 10
）. 这条路径不能和根节点20一起构成一条新的路径. 所以得出的解是最大和（20 +
23 = 43）， 但是却不是一条有效路径。
请大家帮忙看一下是不是我哪算的有问题？ 谢谢。

【在 h****n 的大作中提到】
: 面试写成这样子就挂了
: class Solution {
: public:
: int maxPathSum(TreeNode *root) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: int res;
: int g;
:
: res = helper(root, g);
avatar
t*a
21 楼
要不说我就不会去较这个劲呢,你想啊,他是他爸妈生的,先干掉我不是很正常吗?呵呵,
为了不让他干掉,还是乖点

【在 m********n 的大作中提到】
: 哦，问个逻辑问题
: 如果你们夫妻俩都觉得对方才是过一辈子的人，那你老公怎么会为了父母把你干掉阿？
: 好吧，我承认你们家庭关系挺好，但这真跟你的理论没啥关系
: 主要是你们俩都看得开
: 要是俩都看不开的，就算也觉得对方重要的不得了，肯定也不安宁
avatar
i*e
22 楼
不好意思是我算错了

【在 i******e 的大作中提到】
: 20
: / \
: -3 -5
: / \
: 3 8
: / \ \
: -2 -1 10
: / /
: 6 -7
: 这个test case的max path sum 应该是20-> -3 -> 8 -> 10 (sum = 35).
avatar
g*9
23 楼
as long as the Male 看得开, marriage may continue
avatar
p*n
24 楼
说得非常实在，男人有时也会很脆弱，多给些关爱，不要苛责他，他会记住你的好的。
另外男人的倔脾气就是要顺着他好了，男人像个孩子，心血来潮了会特别想做一件事，
就别拦着。

【在 t********a 的大作中提到】
: 经常看大家的故事,有感动的有气愤的有无聊的,也想和大家说一说我的看法.
: 和老公的关系是至关重要的,他才是那个要和你过一辈子的人,你的公公婆婆你的爸爸妈
: 妈,不管我们多么希望永远和他们在一起,但是老天爷不答应.自己的爸爸妈妈当然是至
: 爱的,老公即使不是至爱的,但他是要和你日夜陪伴,一生一世的.
: 所以无论遇到什么矛盾(和公婆或其他)我都不会把他逼到一个痛苦的境地,如果公婆做
: 了伤害我们的事我会无意地说出来,但我一看到他为难的表情,我就会给他台阶"哎,其实
: 也没什么,老人家我们也别和他们计较了",他反而会说"他们真的讨厌,我去说他们",我
: 当然不会让他去说他们,我老公心里有数就行了呗.反之你要是非要他和你一起说他爸妈
: 的闲话,逼急了他先把你干掉了,要知道,那是他爸妈! 有时候我也会叨唠叨唠我父母无
: 关紧要的缺点,让他知道父母也是可以被叨唠的.
avatar
t*a
25 楼
这位楼上的是知音啊

【在 p********n 的大作中提到】
: 说得非常实在，男人有时也会很脆弱，多给些关爱，不要苛责他，他会记住你的好的。
: 另外男人的倔脾气就是要顺着他好了，男人像个孩子，心血来潮了会特别想做一件事，
: 就别拦着。
avatar
i*r
26 楼
不是个个女人都能看得开放得下的。
sigh
avatar
g*9
27 楼
筋骨都连着，断是想都不敢想地，忍一忍让一让就过去了。

【在 s******d 的大作中提到】
: 对啊，我们改变不了别人，但可以完善自己，如果努力了还是不行（对方的原因或是环
: 境的原因），那就不要拖泥带水了，当断则断
avatar
g*e
28 楼
就是这么个理。
avatar
L*f
29 楼
LZ这样的好女人很难得。
祝福你的一家和美幸福。
一个男人，最重要的要
娶个贤惠的妻子。漂亮
与否，其实不重要。
没有任何人的一生会是
一帆风顺。人生总有起伏。
在人生的低谷时，有个贤惠
的妻子，你就能重新站起来，
迈向人生的下一个高峰。
如果没有一个贤惠的妻子，
你可能就会被打垮，永远
不能重新站立。

【在 t********a 的大作中提到】
: 经常看大家的故事,有感动的有气愤的有无聊的,也想和大家说一说我的看法.
: 和老公的关系是至关重要的,他才是那个要和你过一辈子的人,你的公公婆婆你的爸爸妈
: 妈,不管我们多么希望永远和他们在一起,但是老天爷不答应.自己的爸爸妈妈当然是至
: 爱的,老公即使不是至爱的,但他是要和你日夜陪伴,一生一世的.
: 所以无论遇到什么矛盾(和公婆或其他)我都不会把他逼到一个痛苦的境地,如果公婆做
: 了伤害我们的事我会无意地说出来,但我一看到他为难的表情,我就会给他台阶"哎,其实
: 也没什么,老人家我们也别和他们计较了",他反而会说"他们真的讨厌,我去说他们",我
: 当然不会让他去说他们,我老公心里有数就行了呗.反之你要是非要他和你一起说他爸妈
: 的闲话,逼急了他先把你干掉了,要知道,那是他爸妈! 有时候我也会叨唠叨唠我父母无
: 关紧要的缺点,让他知道父母也是可以被叨唠的.
avatar
C*2
30 楼
Very practical. Good attitude.

【在 t********a 的大作中提到】
: 经常看大家的故事,有感动的有气愤的有无聊的,也想和大家说一说我的看法.
: 和老公的关系是至关重要的,他才是那个要和你过一辈子的人,你的公公婆婆你的爸爸妈
: 妈,不管我们多么希望永远和他们在一起,但是老天爷不答应.自己的爸爸妈妈当然是至
: 爱的,老公即使不是至爱的,但他是要和你日夜陪伴,一生一世的.
: 所以无论遇到什么矛盾(和公婆或其他)我都不会把他逼到一个痛苦的境地,如果公婆做
: 了伤害我们的事我会无意地说出来,但我一看到他为难的表情,我就会给他台阶"哎,其实
: 也没什么,老人家我们也别和他们计较了",他反而会说"他们真的讨厌,我去说他们",我
: 当然不会让他去说他们,我老公心里有数就行了呗.反之你要是非要他和你一起说他爸妈
: 的闲话,逼急了他先把你干掉了,要知道,那是他爸妈! 有时候我也会叨唠叨唠我父母无
: 关紧要的缺点,让他知道父母也是可以被叨唠的.
avatar
B*n
31 楼
如果哪天心血来潮领回来一个小三，外面要养一二奶，也别拦着？
也就问问，其实真要拦，也拦不住不是

【在 p********n 的大作中提到】
: 说得非常实在，男人有时也会很脆弱，多给些关爱，不要苛责他，他会记住你的好的。
: 另外男人的倔脾气就是要顺着他好了，男人像个孩子，心血来潮了会特别想做一件事，
: 就别拦着。
相关阅读
狗家最近team match变慢了吗火坑专业关于职业的规划和思考——欢迎建议和讨论大家说说怎么提防烙印聊点实际的，码农出货量。 (转载)爱彼迎，哈哈哈想来西雅图大公司不？NVIDIA 招 Senior Signal & Power Integrity Engineer现在在ccc，如果回国，签证还能过吗？问个问题吴恩达离开百度，楼天成怎么办？level decided by salary?[内推组内两个opening] Java Developer现在码工不值钱了啊 (转载)Senior business analyst 在湾区的工资水平我接触到的台湾人对大陆的感觉分三类。。 (转载)玩蛋了, trump 把千老的funding要砍掉30%该不该接这个offer？软件公司的名字能预示成功与否谁给总结一下，U家这一年出了多少抓码？如何公司内部调动，求建议
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。