m*******1
发帖数: 77 | 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*****2
发帖数: 21240 | |
D**f
发帖数: 439 | 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*******1
发帖数: 77 | 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***m
发帖数: 5987 | |
p*****2
发帖数: 21240 | 6
是
【在 b***m 的大作中提到】
: 树里面可以是任何数？正数？负数？零？
|
p*****2
发帖数: 21240 | 7
你是对的。
【在 m*******1 的大作中提到】
: MaxTopDown(pNode) 为什么一定要从root 到leaf呢？只要从root开始到任意一个位置
: 都可以啊
|
l*****a
发帖数: 14598 | 8
你是对的。
====================
真的吗？为什么要root开始呢，任两点都可以啊
【在 m*******1 的大作中提到】
: MaxTopDown(pNode) 为什么一定要从root 到leaf呢？只要从root开始到任意一个位置
: 都可以啊
|
t*********n
发帖数: 89 | 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******i
发帖数: 76 | 10 1. 计算以当前节点为根的subtree的最大值，左右孩子都考虑
2. 更新最终最大值
3. 返回当前节点单条路径所能形成的最大值， 即只考虑一个孩子（如果两个孩子节点
都为负数，则返回当前节点的值）
递归 |
|
|
p*****2
发帖数: 21240 | 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********t
发帖数: 5706 | 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*****2
发帖数: 21240 | 13
我的应该也不经过吧？
【在 c********t 的大作中提到】
: 2爷，你的解法和以前人的好像不太一样。关键问题是，如果最大path在左子树中，这
: 个path要不要经过root? 别人的都不经过，你的似乎经过。
|
c********t
发帖数: 5706 | 14 你用leetcode oj 测测
【在 p*****2 的大作中提到】
:
: 我的应该也不经过吧？
|
p*****2
发帖数: 21240 | 15
你测过吗？
【在 c********t 的大作中提到】
: 你用leetcode oj 测测
|
b***m
发帖数: 5987 | 16 二爷的解法应该是对的，任何子树max为负就不计入。这题应该算是一维数组求最大sum
的变种吧？ |
b***m
发帖数: 5987 | 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********t
发帖数: 5706 | 18 我拿你的测了一下，small cases 20个，10个对，10个错
【在 p*****2 的大作中提到】
:
: 你测过吗？
|
p*****2
发帖数: 21240 | 19
不可能吧？我下午刚测过。
【在 c********t 的大作中提到】
: 我拿你的测了一下，small cases 20个，10个对，10个错
|
c********t
发帖数: 5706 | 20 哦，明白了，我测得有问题。
你的这个解太牛了，我花了很久，读了以前的帖子，才明白。理解以后，觉得好简练，
而且其实也很容易理解。
佩服！
有一道变体题，最大路径定义为“两点间最大路径sum1,加上common ancestor到root的
路径。”请问可有好的解？
【在 p*****2 的大作中提到】
:
: 不可能吧？我下午刚测过。
|
|
|
h**********y
发帖数: 1293 | 21 我测了一下也是 10对10错，
你怎么弄的？哪儿的问题阿？
【在 c********t 的大作中提到】
: 哦，明白了，我测得有问题。
: 你的这个解太牛了，我花了很久，读了以前的帖子，才明白。理解以后，觉得好简练，
: 而且其实也很容易理解。
: 佩服！
: 有一道变体题，最大路径定义为“两点间最大路径sum1,加上common ancestor到root的
: 路径。”请问可有好的解？
|
p*****2
发帖数: 21240 | 22
估计你两个都是忘记reset变量了吧？
【在 h**********y 的大作中提到】
: 我测了一下也是 10对10错，
: 你怎么弄的？哪儿的问题阿？
|
h**********y
发帖数: 1293 | 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*****2
发帖数: 21240 | 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**********y
发帖数: 1293 | 25 改了dfs函数名
然后加了个max
【在 p*****2 的大作中提到】
:
: 直接就能运行吗？
|
m******s
发帖数: 21 | 26 可以不可以是空Path？
比如只有一个节点 -3， 那结果是-3 还是0 ？ |
w***o
发帖数: 109 | 27 二爷节省惯了，能省的都省了。要这么测：
max = Integer.MIN_VALUE;
dfs(root);
return max; |
