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 的大作中提到】
: 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 的大作中提到】
: 你的标题中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 的大作中提到】
: 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 的大作中提到】
: binary tree 还是BST?
: 每个node上的值一定是正数吗？
:
: root
: subtree
|
g**u
发帖数: 583 | 6
赞！
flexme 介意和大家分享下面经不？
【在 f****e 的大作中提到】
: 你的标题中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 的大作中提到】
: 你的标题中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 的大作中提到】
: 你的标题中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 的大作中提到】
: 赞! 思路和代码都很简洁。
: 不过我觉得有个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 的大作中提到】
: 你的标题中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 的大作中提到】
: 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 的大作中提到】
: 你的标题中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 的大作中提到】
: 这一行看不大懂。
: f = max(f, leftG + rightG + root->val);
: 不应该是f = max(f, max(leftG, rightG) + root->val);吗？
|
d*********g
发帖数: 154 | 17
这样貌似就对了～～学习了！
【在 l*********8 的大作中提到】
: 赞! 思路和代码都很简洁。
: 不过我觉得有个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 的大作中提到】
: 看这个式子：
: 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 的大作中提到】
: 是吗，你测试了？
|
m*****k
发帖数: 731 | 20 seems a tree version of SubArrayLargestSum problem.
root
subtree
【在 d*********g 的大作中提到】
: 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 的大作中提到】
: 赞! 思路和代码都很简洁。
: 不过我觉得有个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 的大作中提到】
: 这道题是问max path， 还是max subtree？
: 用简单的case test
: 4
: / \
: 5 6
: 如果是max path, 我感觉应该返回 10，你的代码返回的是15
|
l*****i
发帖数: 136 | 23 知道了，谢谢
subtree
【在 l*********8 的大作中提到】
: 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 的大作中提到】
: 你的标题中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 的大作中提到】
: 赞! 思路和代码都很简洁。
: 不过我觉得有个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 的大作中提到】
: How about binary tree with all nodes with negative values?
|
l*********8
发帖数: 4642 | 29 我之前也问了这个问题。
Flexme的程序（和我修改的程序）在这种情况下返回empty path, sum为0.
如果不允许empty path, 那么程序要略作修改，要多加几句。
【在 i**********e 的大作中提到】
: How about binary tree with all nodes with negative values?
|
p*****2
发帖数: 21240 | 30
我也在考虑这个问题。程序需要改动一下。
【在 l*********8 的大作中提到】
: 我之前也问了这个问题。
: 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 的大作中提到】
:
: 我也在考虑这个问题。程序需要改动一下。
|
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 的大作中提到】
:
: 我写了一下，大数据有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 的大作中提到】
: 这是因为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 的大作中提到】
: java 因为不能传地址，好像写不出来，只能对g和f各写一个method
|
