d*********g 发帖数: 154 | 1 How to find maximum path sum in a binary tree.
The path need not be a top-bottom, can start and end nodes need not be root
or leaf, path can start in left/right subtree and end in right/left subtree
wrt any node.
Careercup上看到的,感觉里面没有正确的解答。求版里大神指教。题目里如果没有最
后一句话就好办了,加上最后那句话感觉好复杂。 |
f****e 发帖数: 34 | 2 你的标题中BST有误... 这题是G家面我的题....
用f[i]表示根节点为i的子树种的max path sum.
那么
f[i]=max(f[left[i]], f[right[i]], g[left[i]]+g[right[i]]+w[i])
其中w[i]表示i节点的权重,g[x]表示从节点x,只能往下走,能够走出的最大的path
sum.
代码也很好些
int solve(TreeNode *root, int &g) {
if (!root) {
g = 0;
return 0;
}
int f = 0;
int leftG = 0, rightG = 0;
if (root->left) f = max(f, solve(root->left, leftG));
if (root->right) f = max(f, solve(root->right, rightG);
f = max(f, leftG + rightG + root->val);
g = root->val + max(leftG, rightG);
return f;
}
int solve(TreeNode *root) {
int g;
return solve(root, g);
}
root
subtree
【在 d*********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : How to find maximum path sum in a binary tree. : The path need not be a top-bottom, can start and end nodes need not be root : or leaf, path can start in left/right subtree and end in right/left subtree : wrt any node. : Careercup上看到的,感觉里面没有正确的解答。求版里大神指教。题目里如果没有最 : 后一句话就好办了,加上最后那句话感觉好复杂。
|
p*****2 发帖数: 21240 | 3
这个貌似很牛逼。
【在 f****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的标题中BST有误... 这题是G家面我的题.... : 用f[i]表示根节点为i的子树种的max path sum. : 那么 : f[i]=max(f[left[i]], f[right[i]], g[left[i]]+g[right[i]]+w[i]) : 其中w[i]表示i节点的权重,g[x]表示从节点x,只能往下走,能够走出的最大的path : sum. : 代码也很好些 : int solve(TreeNode *root, int &g) { : if (!root) { : g = 0;
|
l*********8 发帖数: 4642 | 4 binary tree 还是BST?
每个node上的值一定是正数吗?
root
subtree
【在 d*********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : How to find maximum path sum in a binary tree. : The path need not be a top-bottom, can start and end nodes need not be root : or leaf, path can start in left/right subtree and end in right/left subtree : wrt any node. : Careercup上看到的,感觉里面没有正确的解答。求版里大神指教。题目里如果没有最 : 后一句话就好办了,加上最后那句话感觉好复杂。
|
l*********8 发帖数: 4642 | 5 如果每个node的值都是负数,maximum sum path是个empty path(sum是0)吗?
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : binary tree 还是BST? : 每个node上的值一定是正数吗? : : root : subtree
|
g**u 发帖数: 583 | 6
赞!
flexme 介意和大家分享下面经不?
【在 f****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的标题中BST有误... 这题是G家面我的题.... : 用f[i]表示根节点为i的子树种的max path sum. : 那么 : f[i]=max(f[left[i]], f[right[i]], g[left[i]]+g[right[i]]+w[i]) : 其中w[i]表示i节点的权重,g[x]表示从节点x,只能往下走,能够走出的最大的path : sum. : 代码也很好些 : int solve(TreeNode *root, int &g) { : if (!root) { : g = 0;
|
l*********8 发帖数: 4642 | |
l*********8 发帖数: 4642 | |
c********t 发帖数: 5706 | 9 赞,太简洁了。
【在 f****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的标题中BST有误... 这题是G家面我的题.... : 用f[i]表示根节点为i的子树种的max path sum. : 那么 : f[i]=max(f[left[i]], f[right[i]], g[left[i]]+g[right[i]]+w[i]) : 其中w[i]表示i节点的权重,g[x]表示从节点x,只能往下走,能够走出的最大的path : sum. : 代码也很好些 : int solve(TreeNode *root, int &g) { : if (!root) { : g = 0;
|
l*********8 发帖数: 4642 | 10 赞! 思路和代码都很简洁。
不过我觉得有个bug:
g = root->val + max(leftG, rightG);
应该为:
g = max(0, root->val + max(leftG, rightG));
test case:
1
\
5
\
-7
答案应该是6,本程序返回5.
另外, if (root->left)也可以去掉。
试在你的基础上修改如下:
int solve(TreeNode *root, int &g) {
if (!root) {
g = 0;
return 0;
}
int leftG = 0, rightG = 0;
int f = max(solve(root->left, leftG),solve(root->right, rightG);
f = max(f, leftG + rightG + root->val);
g = max(0, root->val + max(leftG, rightG));
return f;
}
int solve(TreeNode *root) {
int g;
return solve(root, g);
}
【在 f****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的标题中BST有误... 这题是G家面我的题.... : 用f[i]表示根节点为i的子树种的max path sum. : 那么 : f[i]=max(f[left[i]], f[right[i]], g[left[i]]+g[right[i]]+w[i]) : 其中w[i]表示i节点的权重,g[x]表示从节点x,只能往下走,能够走出的最大的path : sum. : 代码也很好些 : int solve(TreeNode *root, int &g) { : if (!root) { : g = 0;
|
|
|
p*****2 发帖数: 21240 | |
f****e 发帖数: 34 | 12 啊,确实 那个地方是个bug。
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 赞! 思路和代码都很简洁。 : 不过我觉得有个bug: : g = root->val + max(leftG, rightG); : 应该为: : g = max(0, root->val + max(leftG, rightG)); : test case: : 1 : \ : 5 : \
|
c********t 发帖数: 5706 | 13 java 因为不能传地址,好像写不出来,只能对g和f各写一个method
【在 f****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的标题中BST有误... 这题是G家面我的题.... : 用f[i]表示根节点为i的子树种的max path sum. : 那么 : f[i]=max(f[left[i]], f[right[i]], g[left[i]]+g[right[i]]+w[i]) : 其中w[i]表示i节点的权重,g[x]表示从节点x,只能往下走,能够走出的最大的path : sum. : 代码也很好些 : int solve(TreeNode *root, int &g) { : if (!root) { : g = 0;
|
f****e 发帖数: 34 | 14 可以返回一个结构体,比如C++的话返回pair
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : java 因为不能传地址,好像写不出来,只能对g和f各写一个method
|
l*****a 发帖数: 559 | 15 这一行看不大懂。
f = max(f, leftG + rightG + root->val);
不应该是f = max(f, max(leftG, rightG) + root->val);吗?
【在 f****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的标题中BST有误... 这题是G家面我的题.... : 用f[i]表示根节点为i的子树种的max path sum. : 那么 : f[i]=max(f[left[i]], f[right[i]], g[left[i]]+g[right[i]]+w[i]) : 其中w[i]表示i节点的权重,g[x]表示从节点x,只能往下走,能够走出的最大的path : sum. : 代码也很好些 : int solve(TreeNode *root, int &g) { : if (!root) { : g = 0;
|
f****e 发帖数: 34 | 16 看这个式子:
f[i]=max(f[left[i]], f[right[i]], g[left[i]]+g[right[i]]+w[i])
leftG就是g[left[i]], rightG就是g[right[i]]
思路就是当考虑根节点为i的子树的max path sum是,有3种情况:
1. path不经过根节点,那么它要么完全在左子树中,要么完全在右子树中
a。 如果完全在左子树中,那么就是f[left[i]]
b。如果完全在右子树中,那么就是f[right[i]]
2.如果path经过根结点,那么答案就是g[left[i]]+g[right[i]]+w[i]
g[left[i]]表示从i的左结点开始,一直往下走,能够达到的max sum
g[right[i]]类似
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这一行看不大懂。 : f = max(f, leftG + rightG + root->val); : 不应该是f = max(f, max(leftG, rightG) + root->val);吗?
|
d*********g 发帖数: 154 | 17
这样貌似就对了~~学习了!
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 赞! 思路和代码都很简洁。 : 不过我觉得有个bug: : g = root->val + max(leftG, rightG); : 应该为: : g = max(0, root->val + max(leftG, rightG)); : test case: : 1 : \ : 5 : \
|
l*****a 发帖数: 559 | 18 明白了,题意理解错了。
path可以有任意节点起始,任意节点终止。
【在 f****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看这个式子: : f[i]=max(f[left[i]], f[right[i]], g[left[i]]+g[right[i]]+w[i]) : leftG就是g[left[i]], rightG就是g[right[i]] : 思路就是当考虑根节点为i的子树的max path sum是,有3种情况: : 1. path不经过根节点,那么它要么完全在左子树中,要么完全在右子树中 : a。 如果完全在左子树中,那么就是f[left[i]] : b。如果完全在右子树中,那么就是f[right[i]] : 2.如果path经过根结点,那么答案就是g[left[i]]+g[right[i]]+w[i] : g[left[i]]表示从i的左结点开始,一直往下走,能够达到的max sum : g[right[i]]类似
|
s********k 发帖数: 6180 | 19 sorry,自己算错了
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是吗,你测试了?
|
m*****k 发帖数: 731 | 20 seems a tree version of SubArrayLargestSum problem.
root
subtree
【在 d*********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : How to find maximum path sum in a binary tree. : The path need not be a top-bottom, can start and end nodes need not be root : or leaf, path can start in left/right subtree and end in right/left subtree : wrt any node. : Careercup上看到的,感觉里面没有正确的解答。求版里大神指教。题目里如果没有最 : 后一句话就好办了,加上最后那句话感觉好复杂。
|
|
|
l*****i 发帖数: 136 | 21 这道题是问max path, 还是max subtree?
用简单的case test
4
/ \
5 6
如果是max path, 我感觉应该返回 10,你的代码返回的是15
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 赞! 思路和代码都很简洁。 : 不过我觉得有个bug: : g = root->val + max(leftG, rightG); : 应该为: : g = max(0, root->val + max(leftG, rightG)); : test case: : 1 : \ : 5 : \
|
l*********8 发帖数: 4642 | 22 path 是5 4 6
看题目:
“The path need not be a top-bottom, can start and end nodes need not be
root
or leaf, path can start in left/right subtree and end in right/left subtree
wrt any node.”
【在 l*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这道题是问max path, 还是max subtree? : 用简单的case test : 4 : / \ : 5 6 : 如果是max path, 我感觉应该返回 10,你的代码返回的是15
|
l*****i 发帖数: 136 | 23 知道了,谢谢
subtree
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : path 是5 4 6 : 看题目: : “The path need not be a top-bottom, can start and end nodes need not be : root : or leaf, path can start in left/right subtree and end in right/left subtree : wrt any node.”
|
h*****f 发帖数: 248 | 24 #include
struct Node {
int value;
Node* pLeft;
Node* pRight;
};
int findMaxSubTree(Node* pNode, int& maxSoFar) {
if (!pNode) return 0;
int leftSum = findMaxSubTree(pNode->pLeft, maxSoFar);
int rightSum = findMaxSubTree(pNode->pRight, maxSoFar);
int currentSum = pNode->value + std::max(0, leftSum) + std::max(0,
rightSum);
maxSoFar = std::max(currentSum, maxSoFar);
return currentSum;
}
int main() {
Node node4 = {4, NULL, NULL};
Node node3 = {3, NULL, NULL};
Node node6 = {6, &node4, &node3};
Node nodeMinus7 = {-7, &node6, NULL};
Node node5 = {5, &nodeMinus7, NULL};
int maxSoFar = 0;
findMaxSubTree(&node5, maxSoFar);
std::cout << maxSoFar << std::endl;
}
Just curious, what test cases are required to ensure the correctiveness if
the interviewer asks? |
S********t 发帖数: 3431 | 25 这题是我最近几次面别人挺喜欢用的一道
【在 f****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的标题中BST有误... 这题是G家面我的题.... : 用f[i]表示根节点为i的子树种的max path sum. : 那么 : f[i]=max(f[left[i]], f[right[i]], g[left[i]]+g[right[i]]+w[i]) : 其中w[i]表示i节点的权重,g[x]表示从节点x,只能往下走,能够走出的最大的path : sum. : 代码也很好些 : int solve(TreeNode *root, int &g) { : if (!root) { : g = 0;
|
e***s 发帖数: 799 | 26 它是伟大的
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 赞! 思路和代码都很简洁。 : 不过我觉得有个bug: : g = root->val + max(leftG, rightG); : 应该为: : g = max(0, root->val + max(leftG, rightG)); : test case: : 1 : \ : 5 : \
|
i**********e 发帖数: 1145 | 27 How about binary tree with all nodes with negative values? |
s********0 发帖数: 34 | 28 In that case, i think it should return the max one among all the negative.
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : How about binary tree with all nodes with negative values?
|
l*********8 发帖数: 4642 | 29 我之前也问了这个问题。
Flexme的程序(和我修改的程序)在这种情况下返回empty path, sum为0.
如果不允许empty path, 那么程序要略作修改,要多加几句。
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : How about binary tree with all nodes with negative values?
|
p*****2 发帖数: 21240 | 30
我也在考虑这个问题。程序需要改动一下。
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我之前也问了这个问题。 : Flexme的程序(和我修改的程序)在这种情况下返回empty path, sum为0. : 如果不允许empty path, 那么程序要略作修改,要多加几句。
|
|
|
i**********e 发帖数: 1145 | 31 好题。OJ 已经加上这题了。
要改动的话只要把 f 初始为 INT_MIN 就可以了。至于空树的情况,特别处理一下就行
。 |
p*****2 发帖数: 21240 | 32
我写了一下,大数据有run time error.
int[] dfs(TreeNode root)
{
int[] ans=new int[2];
Arrays.fill(ans, Integer.MIN_VALUE);
if(root!=null)
{
int[] l_ans=dfs(root.left);
int[] r_ans=dfs(root.right);
ans[0]=Math.max(l_ans[0], r_ans[0]);
ans[1]=Math.max(l_ans[1], r_ans[1]);
ans[1]=ans[1]<0?root.val:root.val+ans[1];
int m=root.val;
if(l_ans[1]>0)
m+=l_ans[1];
if(r_ans[1]>0)
m+=r_ans[1];
ans[0]=Math.max(ans[0], m);
}
return ans;
}
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我也在考虑这个问题。程序需要改动一下。
|
l*****a 发帖数: 559 | 33 int maxPathSum(TreeNode *root) {
int d = 0;
return maxPathSum(root, d);
}
int maxPathSum(TreeNode *node, int &depth){
if(node == NULL){
depth = 0;
return INT_MIN;
}
int dl = 0;
int fl = maxPathSum(node->left, dl);
int dr = 0;
int fr = maxPathSum(node->right, dr);
int f = max(fl, max(fr, dl + node->val + dr));
depth = max(max(dl, dr) + node->val, 0);
return f;
} |
h****n 发帖数: 1093 | 34 贴一个通过OJ的版本,能处理全部负数的情况
楼主的版本很牛逼,不过有个大的bug,就是递归的结束条件没法达到,因为调用前判
断是不是指针为空了,不为空才调用,但是需要为空的时候才能达到递归结束条件
g才能正确的自底向上
/**
* 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 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;
}
}; |
i**********e 发帖数: 1145 | 35 这是因为stack overflow了。
我已经重新设计那个最大的large case,你程序现在可以过了。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我写了一下,大数据有run time error. : int[] dfs(TreeNode root) : { : int[] ans=new int[2]; : Arrays.fill(ans, Integer.MIN_VALUE); : if(root!=null) : { : int[] l_ans=dfs(root.left); : int[] r_ans=dfs(root.right);
|
p*****2 发帖数: 21240 | 36
多谢大牛。
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这是因为stack overflow了。 : 我已经重新设计那个最大的large case,你程序现在可以过了。
|
m******2 发帖数: 1007 | 37 写个为代码, currentMax 是地址
F(node n, currentMax)
if n == Null
return -MAX_INT
leftMax = F(n.left, currentMax )
rightMax = F(n.right, currentMax )
currentMax = max(n.value,
n.value+ leftMax,
n.value + rightMax,
n.value+ leftMax + rightMax,
currentMax , )
return max(0, n.value+ leftMax, n.value + rightMax,n.value ) |
d*********4 发帖数: 409 | |
d*********4 发帖数: 409 | 39 我在java里面设置了一个class property,每次更新那个property,等到结果出来再把
那个property初始化。
我试着把f和g单独写,leetcode上面large judge过不了,因为递归套递归,O(n^2)了
吧。
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : java 因为不能传地址,好像写不出来,只能对g和f各写一个method
|