Binary Tree Maximum Path Sum - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum# JobHunting - 待字闺中

m*12012-11-11 08:11

1 楼

Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
1
/ \
2 3
Return 6.
leetcode 上面的一道题，求大神们解释啊

p*22012-11-11 08:11

2 楼

这题前几天刚讨论过。

D*f2012-11-11 08:11

3 楼

MaxSum(pNode) = max {MaxSum(pNode->L), MaxSum(pNode->R), pNode->V +
MaxTopDown(pNode->L) + MaxTopDown(pNode->R) }
MaxTopDown(pNode) is the max sum of path from root to leaf in this tree.

m*12012-11-11 08:11

4 楼

MaxTopDown(pNode) 为什么一定要从root 到leaf呢？只要从root开始到任意一个位置
都可以啊

【在 D**f 的大作中提到】

: MaxSum(pNode) = max {MaxSum(pNode->L), MaxSum(pNode->R), pNode->V +
: MaxTopDown(pNode->L) + MaxTopDown(pNode->R) }
: MaxTopDown(pNode) is the max sum of path from root to leaf in this tree.

b*m2012-11-11 08:11

5 楼

树里面可以是任何数？正数？负数？零？

p*22012-11-11 08:11

6 楼

是

【在 b***m 的大作中提到】

: 树里面可以是任何数？正数？负数？零？

p*22012-11-11 08:11

7 楼

你是对的。

【在 m*******1 的大作中提到】

: MaxTopDown(pNode) 为什么一定要从root 到leaf呢？只要从root开始到任意一个位置
: 都可以啊

l*a2012-11-11 08:11

8 楼

你是对的。
====================
真的吗？为什么要root开始呢，任两点都可以啊

【在 m*******1 的大作中提到】

: MaxTopDown(pNode) 为什么一定要从root 到leaf呢？只要从root开始到任意一个位置
: 都可以啊

t*n2012-11-11 08:11

9 楼

贴个我写的代码，将就看了。
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int max = INT_MIN;
maxPath(root,max);
return max;
}
int maxPath(TreeNode *root,int &max){
if (!root)
return 0;
int l = maxPath(root->left,max);
int r = maxPath(root->right,max);
if ((l+r+root->val)>max){
max = l+r+root->val;
}
int big = l>r?(l+root->val):(r+root->val);
return big>0?big:0;
}

d*i2012-11-11 08:11

10 楼

1. 计算以当前节点为根的subtree的最大值，左右孩子都考虑
2. 更新最终最大值
3. 返回当前节点单条路径所能形成的最大值，即只考虑一个孩子（如果两个孩子节点
都为负数，则返回当前节点的值）
递归

p*22012-11-11 08:11

11 楼

int dfs(TreeNode root)
{
if(root==null)
return 0;

int l=dfs(root.left);
int r=dfs(root.right);
int m=root.val;
if(l>0) m+=l;
if(r>0) m+=r;

max=Math.max(max,m);
return Math.max(l,r)>0?Math.max(l,r)+root.val:root.val;
}

c*t2012-11-11 08:11

12 楼

2爷，你的解法和以前人的好像不太一样。关键问题是，如果最大path在左子树中，这
个path要不要经过root? 别人的都不经过，你的似乎经过。

【在 p*****2 的大作中提到】

: int dfs(TreeNode root)
: {
: if(root==null)
: return 0;
:
: int l=dfs(root.left);
: int r=dfs(root.right);
: int m=root.val;
: if(l>0) m+=l;
: if(r>0) m+=r;

p*22012-11-11 08:11

13 楼

我的应该也不经过吧？

【在 c********t 的大作中提到】

: 2爷，你的解法和以前人的好像不太一样。关键问题是，如果最大path在左子树中，这
: 个path要不要经过root? 别人的都不经过，你的似乎经过。

c*t2012-11-11 08:11

14 楼

你用leetcode oj 测测

【在 p*****2 的大作中提到】

:
: 我的应该也不经过吧？

p*22012-11-11 08:11

15 楼

你测过吗？

【在 c********t 的大作中提到】

: 你用leetcode oj 测测

b*m2012-11-11 08:11

16 楼

二爷的解法应该是对的，任何子树max为负就不计入。这题应该算是一维数组求最大sum
的变种吧？

b*m2012-11-11 08:11

17 楼

我的这个code貌似跟二爷的意思一样？
int g_nMax = MIN_INT;
int MaxPathSum(Node *pNode)
{
if( !pNode ) return 0;

int nMaxLeft = MaxPathSum(pNode->pLeft);
int nMaxRight = MaxPathSum(pNode->pRight);
int nMaxCurrent = pNode->data + max(0, nMaxLeft) + max(0, nMaxRight);
g_nMax = max(g_nMax, nMaxCurrent);

int nMaxLeftRight = max(nMaxLeft, nMaxRight);
return nMaxLeftRight > 0 ? nMaxLeftRight + pNode->data : pNode->data;
}

c*t2012-11-11 08:11

18 楼

我拿你的测了一下，small cases 20个，10个对，10个错

【在 p*****2 的大作中提到】

:
: 你测过吗？

p*22012-11-11 08:11

19 楼

不可能吧？我下午刚测过。

【在 c********t 的大作中提到】

: 我拿你的测了一下，small cases 20个，10个对，10个错

c*t2012-11-11 08:11

20 楼

哦，明白了，我测得有问题。
你的这个解太牛了，我花了很久，读了以前的帖子，才明白。理解以后，觉得好简练，
而且其实也很容易理解。
佩服！
有一道变体题，最大路径定义为“两点间最大路径sum1,加上common ancestor到root的
路径。”请问可有好的解？

【在 p*****2 的大作中提到】

:
: 不可能吧？我下午刚测过。

h*y2012-11-11 08:11

21 楼

我测了一下也是 10对10错，
你怎么弄的？哪儿的问题阿？

【在 c********t 的大作中提到】

: 哦，明白了，我测得有问题。
: 你的这个解太牛了，我花了很久，读了以前的帖子，才明白。理解以后，觉得好简练，
: 而且其实也很容易理解。
: 佩服！
: 有一道变体题，最大路径定义为“两点间最大路径sum1,加上common ancestor到root的
: 路径。”请问可有好的解？

p*22012-11-11 08:11

22 楼

估计你两个都是忘记reset变量了吧？

【在 h**********y 的大作中提到】

: 我测了一下也是 10对10错，
: 你怎么弄的？哪儿的问题阿？

h*y2012-11-11 08:11

23 楼

直接用的你的code阿。。哪里要reset？
int dfs(TreeNode root)
{
if(root==null)
return 0;

int l=dfs(root.left);
int r=dfs(root.right);
int m=root.val;
if(l>0) m+=l;
if(r>0) m+=r;

max=Math.max(max,m);
return Math.max(l,r)>0?Math.max(l,r)+root.val:root.val;
}

【在 p*****2 的大作中提到】

:
: 估计你两个都是忘记reset变量了吧？

p*22012-11-11 08:11

24 楼

直接就能运行吗？

【在 h**********y 的大作中提到】

: 直接用的你的code阿。。哪里要reset？
: int dfs(TreeNode root)
: {
: if(root==null)
: return 0;
:
: int l=dfs(root.left);
: int r=dfs(root.right);
: int m=root.val;
: if(l>0) m+=l;

h*y2012-11-11 08:11

25 楼

改了dfs函数名
然后加了个max

【在 p*****2 的大作中提到】

:
: 直接就能运行吗？

m*s2012-11-11 08:11

26 楼

可以不可以是空Path？
比如只有一个节点 -3，那结果是-3 还是0 ？

w*o2012-11-11 08:11

27 楼

二爷节省惯了，能省的都省了。要这么测：
max = Integer.MIN_VALUE;
dfs(root);
return max;