B*******1
发帖数: 2454 | 1 Given a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is
maximum where F(X,Y) = sum of nodes in the path from root to X + sum of
nodes in the path from root to Y - sum of nodes in the common path from root
to first common ancestor of the Nodes X and Y | S********t
发帖数: 3431 | 2 not hard if someone is used to thinking recursively.
root
【在 B*******1 的大作中提到】
: Given a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is
: maximum where F(X,Y) = sum of nodes in the path from root to X + sum of
: nodes in the path from root to Y - sum of nodes in the common path from root
: to first common ancestor of the Nodes X and Y
| w*****3
发帖数: 101 | 3 value 全正
/*
* find the maximum pair
*/
public int F( bn root){
return maxValue(root.left) +maxValue(root.right);;
}
/*
* find the bigest value path from root to the node
*/
public int maxValue( bn root){
if( root == null) return 0;
return root.value + Math.max(maxValue(root.left), maxValue(root.right));
} | w*****3
发帖数: 101 | 4 有负值
HashMap map = new HashMap();
/*
* find the maximum pair
*/
public int solve( btn root){
if(root == null) return 0;
int res = maxValue(root.left) +maxValue(root.right);
res = Math.max(res, solve(root.left));
res = Math.max(res, solve(root.right));
return res;
}
/*
* find the bigest value path from root to the node
*/
public int maxValue( btn root){
if( root == null) return 0;
if(map.containsKey(root)){
return map.get(root);
}
int res = root.value + Math.max(maxValue(root.left), maxValue(root.
right));
map.put(root, res);
return res;
} | i*****f
发帖数: 578 | 5 Good recursion. But looks not exactly what lz asked - X,Y has to be leaf. In
your case what if root only has one child? It measures the distance from
root to deepest child in the right subtree?
【在 w*****3 的大作中提到】
: value 全正
: /*
: * find the maximum pair
: */
: public int F( bn root){
: return maxValue(root.left) +maxValue(root.right);;
: }
: /*
: * find the bigest value path from root to the node
: */
| t******g
发帖数: 252 | 6 Everything is zero.
【在 w*****3 的大作中提到】
: 有负值
: HashMap map = new HashMap();
: /*
: * find the maximum pair
: */
: public int solve( btn root){
: if(root == null) return 0;
: int res = maxValue(root.left) +maxValue(root.right);
: res = Math.max(res, solve(root.left));
: res = Math.max(res, solve(root.right));
| t******g
发帖数: 252 | 7 Never mind.
【在 w*****3 的大作中提到】
: 有负值
: HashMap map = new HashMap();
: /*
: * find the maximum pair
: */
: public int solve( btn root){
: if(root == null) return 0;
: int res = maxValue(root.left) +maxValue(root.right);
: res = Math.max(res, solve(root.left));
: res = Math.max(res, solve(root.right));
| g**********y
发帖数: 14569 | 8 这个code假定X, Y分属root的左右子树？
【在 w*****3 的大作中提到】
: value 全正
: /*
: * find the maximum pair
: */
: public int F( bn root){
: return maxValue(root.left) +maxValue(root.right);;
: }
: /*
: * find the bigest value path from root to the node
: */
| t******g
发帖数: 252 | 9 3 cases should be compared. X, Y both in left subtree, X, Y both in right
subtree, and one from each.
So at each node, the first and second highest pair should be remembered.
【在 g**********y 的大作中提到】
: 这个code假定X, Y分属root的左右子树？
| w*****3
发帖数: 101 | 10 right~~
Thanks for point that out :-)
【在 g**********y 的大作中提到】
: 这个code假定X, Y分属root的左右子树？
| | | t******g
发帖数: 252 | 11 I would also asking questions to clarify the problem.
Can X, Y be the same node?
【在 t******g 的大作中提到】
: 3 cases should be compared. X, Y both in left subtree, X, Y both in right
: subtree, and one from each.
: So at each node, the first and second highest pair should be remembered.
| g**********y
发帖数: 14569 | 12 Basically, need another function like:
public int G(bn root) {
return max(F(root), root.value + G(root.left), root.value + G(root.right
));
}
【在 t******g 的大作中提到】
: 3 cases should be compared. X, Y both in left subtree, X, Y both in right
: subtree, and one from each.
: So at each node, the first and second highest pair should be remembered.
| w*****3
发帖数: 101 | 13 nvm, 理解错误 ....-_-....
【在 t******g 的大作中提到】
: 3 cases should be compared. X, Y both in left subtree, X, Y both in right
: subtree, and one from each.
: So at each node, the first and second highest pair should be remembered.
| B*******1
发帖数: 2454 | 14 谢谢大家的回答，补充，这个tree是complete binary tree， 最佳算法是o(n)的。 | d*******l
发帖数: 338 | 15 对于每个非叶节点，算出对应的maxValue，这个可以O(n)做到。
对于每个非叶节点，用maxValue(leftChild)+maxValue(rightChild)去更新当前最大值
。也可以O(n)做到。
其实本质上就是wwwwar3的方法，保存每个节点的maxValue用到hashmap，如果是完全二
叉树也可以考虑用数组，那这个问题就非常像DP了。
wwwwar3的方法中对于null返回0感觉值得商榷，如果认为X和Y可以是同一个节点那可以
这么做，否则返回负无穷比较合适。 | A***M
发帖数: 18 | 16 我想到的一个办法是比较简单的递归：
int MaxSums(NODE* root, int SumFromRoot, int &MaxSumToLeaf)
{
if (NULL == root)
{
MaxSumToLeaf = 0;
return 0;
}
int CurSumFromRoot = SumFromRoot + root->value;
int LMaxSumToLeaf, RMaxSumToLeaf;
int LeftMax = MaxSums(root->left, CurSumFromRoot, LMaxSumToLeaf);
int RightMax = MaxSums(root->right, CurSumFromRoot, RMaxSumToLeaf);
int NewMaxSumToLeaf = (LMaxSumToLeaf >RMaxSumToLeaf)? LMaxSumToLeaf:
RMaxSumToLeaf;
MaxSumToLeaf = root->value + NewMaxSumToLeaf;
return CurSumFromRoot + LMaxSumToLeaf + RMaxSumToLeaf;
} | d*******l
发帖数: 338 | 17 方法应该是对的，但为什么要加SumFromRoot呢？题目中的要求应该是要减去这一部分
的啊。
【在 A***M 的大作中提到】
: 我想到的一个办法是比较简单的递归：
: int MaxSums(NODE* root, int SumFromRoot, int &MaxSumToLeaf)
: {
: if (NULL == root)
: {
: MaxSumToLeaf = 0;
: return 0;
: }
: int CurSumFromRoot = SumFromRoot + root->value;
: int LMaxSumToLeaf, RMaxSumToLeaf;
| i**********e
发帖数: 1145 | 18 你的基本思路是对的，但是：
1)问题要得到两个叶子节点，不单单只是 maxsum
2)你的代码 assume 所有节点值都是正数
稍微更改一下就好了。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 A***M 的大作中提到】
: 我想到的一个办法是比较简单的递归：
: int MaxSums(NODE* root, int SumFromRoot, int &MaxSumToLeaf)
: {
: if (NULL == root)
: {
: MaxSumToLeaf = 0;
: return 0;
: }
: int CurSumFromRoot = SumFromRoot + root->value;
: int LMaxSumToLeaf, RMaxSumToLeaf;
| i**********e
发帖数: 1145 | 19 刚才写的，没有验证过。。。
typedef pair IntNode;
// precondition: binary tree must be complete. (eg, each node must have
either 0 or 2 children)
IntNode maxSumLeafNodes(Node *root, int sumFromRoot, Node *& leaf1, Node *&
leaf2, int &maxSum) {
assert(root);
// base case: leaf node (no children)
if (!root->left && !root->right) return IntNode(root->data, root);
// must have 2 children
assert(root->left && root->right);
IntNode fromLeft = maxSumLeafNodes(root->left, sumFromRoot + root->data,
leaf1, leaf2, maxSum);
IntNode fromRight = maxSumLeafNodes(root->right, sumFromRoot + root->data,
leaf1, leaf2, maxSum);
int sumFromLeft = fromLeft.first;
int sumFromRight = fromRight.first;
int sumSubtree = root->data + sumFromLeft + sumFromRight;
int sum = sumFromRoot + sumSubtree;
if (sum >= maxSum) {
maxSum = sum;
leaf1 = fromLeft.second;
leaf2 = fromRight.second;
}
return (sumFromLeft > sumFromRight) ?
(IntNode(sumFromLeft + root->data, fromLeft.second)) :
(IntNode(sumFromRight + root->data, fromRight.second));
}
void maxSumLeafNodes(Node *root, Node *& leaf1, Node *& leaf2) {
if (!root) return;
int maxSum = INT_MIN;
maxSumLeafNodes(root, 0, leaf1, leaf2, maxSum);
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | A***M
发帖数: 18 | 20 从题目要求看， SumFromRoot 加两次， 然后又减一次， 其实相当于加一次。
【在 d*******l 的大作中提到】
: 方法应该是对的，但为什么要加SumFromRoot呢？题目中的要求应该是要减去这一部分
: 的啊。
| | | B*******1
发帖数: 2454 | 21 对的,我就是看了你之前的人的解答,全部人都没有加这一部分...
【在 A***M 的大作中提到】
: 从题目要求看， SumFromRoot 加两次， 然后又减一次， 其实相当于加一次。
| d*******l
发帖数: 338 | 22 额，确实，先入为主了，还是不够仔细。
【在 B*******1 的大作中提到】
: 对的,我就是看了你之前的人的解答,全部人都没有加这一部分...
| A***M
发帖数: 18 | 23 1)恩。 是需要改一下。加个参数返回值就可以了
2） 这个我倒没考虑呢。
【在 i**********e 的大作中提到】
: 你的基本思路是对的，但是：
: 1)问题要得到两个叶子节点，不单单只是 maxsum
: 2)你的代码 assume 所有节点值都是正数
: 稍微更改一下就好了。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
| d*******l
发帖数: 338 | 24 没错，还是题目没看清楚，最开始我甚至以为是路径上的节点数目的和。。这样的话，
似乎只要像ihasleetcode说的那样，解决下节点值为负数的情况就可以了，在参数里再
加个值应该就行。
【在 A***M 的大作中提到】
: 从题目要求看， SumFromRoot 加两次， 然后又减一次， 其实相当于加一次。
| i**********e
发帖数: 1145 | 25 第二点我看错了，你的代码是对的，可以返回正确的 maxsum.
关于第一点，我一开始也是跟你一样，base case 判断为 NULL == root。这个如果只
是返回 maxsum 没有问题，但是如果要返回两个叶子节点的话就应该更改下 base case.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 A***M 的大作中提到】
: 1)恩。 是需要改一下。加个参数返回值就可以了
: 2） 这个我倒没考虑呢。
| B*******1
发帖数: 2454 | 26 我看了好久他之前的帖子的code，就是没有看到code里面有加这部分node的和的操作。
【在 d*******l 的大作中提到】
: 没错，还是题目没看清楚，最开始我甚至以为是路径上的节点数目的和。。这样的话，
: 似乎只要像ihasleetcode说的那样，解决下节点值为负数的情况就可以了，在参数里再
: 加个值应该就行。
| d*******d
发帖数: 2050 | 27 我觉得没那么复杂,
没试验过
int maxsum(Node * root, int & maxpathsum, int sumtohere){
if( root== NULL){
maxpathsum = sumtohere;
return 0;
}
int left_maxpathsum = 0;
int left_maxsum = maxsum( root->left, left_maxpathsum, sumtohere+root->v);
int right_maxpathsum = 0;
int right_maxsum = maxsum root->right, right_maxpathsum, sumtohere+root->v
);
maxpathsum = max(left_maxpathsum, right_maxpathsum);
int curmaxsum = left_maxpathsum + right_maxpathsum - sumtohere - root->v;
return max(curmaxsum, left_maxsum, right_maxsum);
}
int find_max(Node * root){
int maxpath;
return maxsum(root,maxpath, 0);
}
root
【在 B*******1 的大作中提到】
: Given a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is
: maximum where F(X,Y) = sum of nodes in the path from root to X + sum of
: nodes in the path from root to Y - sum of nodes in the common path from root
: to first common ancestor of the Nodes X and Y
| i**********e
发帖数: 1145 | 28 还有一点，这题假设 binary tree 是 complete 是有原因的。
complete binary tree 可以保证每个节点必须有０个或者２个孩子。
这样可以保证每个递归都可以有两个 leaf node，也就是一个 solution candidate。
然后再比较两个 leaf node，返回那个路径比较大的给 parent。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | d*******d
发帖数: 2050 | 29 我觉得没有这个必要,按照我上面的code,只有单孩子节点的node, 在递归中会被他的母
节点取代.
【在 i**********e 的大作中提到】
: 还有一点，这题假设 binary tree 是 complete 是有原因的。
: complete binary tree 可以保证每个节点必须有０个或者２个孩子。
: 这样可以保证每个递归都可以有两个 leaf node，也就是一个 solution candidate。
: 然后再比较两个 leaf node，返回那个路径比较大的给 parent。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
| i**********e
发帖数: 1145 | 30 你的代码没有返回两个叶子节点，题目说清楚要找这两个叶子节点。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 d*******d 的大作中提到】
: 我觉得没有这个必要,按照我上面的code,只有单孩子节点的node, 在递归中会被他的母
: 节点取代.
| | | A***M
发帖数: 18 | 31 我也没考虑complete binary tree的因素。
return的 maxsum 是有问题的， 正确的应该是
当前节点的MaxSum = max( CurSumFromRoot + LMaxSumToLeaf + RMaxSumToLeaf,
左节点的maxsum,
右节点的maxsum)
【在 i**********e 的大作中提到】
: 还有一点，这题假设 binary tree 是 complete 是有原因的。
: complete binary tree 可以保证每个节点必须有０个或者２个孩子。
: 这样可以保证每个递归都可以有两个 leaf node，也就是一个 solution candidate。
: 然后再比较两个 leaf node，返回那个路径比较大的给 parent。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
| d*******l
发帖数: 338 | 32 恩，居然大家都没注意到。上面想法一度有些混乱，总结一下，这题可以用递归做，每
个节点的maxsum依赖于3部分，一部分是根节点到它的sum，还有就是它左右子树向下的
最大path的sum，所以参数中要保存根节点到当前的sum，递归的过程中，在向下推的时
候是把这一部分求出来，向上收的时候是计算向下path的最大sum并且更新最大值。这
样应该没错了。
【在 B*******1 的大作中提到】
: 我看了好久他之前的帖子的code，就是没有看到code里面有加这部分node的和的操作。
| d*******l
发帖数: 338 | 33 我觉得如果root==null返回负无穷的话，就不一定需要complete binary tree
【在 i**********e 的大作中提到】
: 还有一点，这题假设 binary tree 是 complete 是有原因的。
: complete binary tree 可以保证每个节点必须有０个或者２个孩子。
: 这样可以保证每个递归都可以有两个 leaf node，也就是一个 solution candidate。
: 然后再比较两个 leaf node，返回那个路径比较大的给 parent。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
| i**********e
发帖数: 1145 | 34 是的，你是对的。
只有单孩子节点的话，那其中一个 lChild or rChild 的 sum 会为０。
但是如果不只是要返回 maxsum，而也返回两个叶子节点的话就要额外判断了。
你的代码是很简洁，但是我说过了，没有达到题目的要求。
题目要求的是返回两个叶子节点，这个你代码不能轻易解决。不是简单地加入额外的两
个返回值就可以了。
【在 d*******d 的大作中提到】
: 我觉得没有这个必要,按照我上面的code,只有单孩子节点的node, 在递归中会被他的母
: 节点取代.
| d*******d
发帖数: 2050 | 35 这好办
int maxsum(Node * root, int & maxpathsum, Node * & maxpathNode,
int sumtohere, Node * & n1, Node * & n2){
if( root== NULL){
maxpathsum = sumtohere;
maxpathNode = NULL;
n1 = NULL;
n2 = NULL;
return 0;
}
int left_maxpathsum = 0;
Node * leftNode1;
Node * leftNode2;
Node * left_maxpathNode;
int left_maxsum = maxsum( root->left, left_maxpathsum, left_maxpathNode,
sumtohere+root->v, leftNode1, leftNode2);
int right_maxpathsum = 0;
Node * rightNode1;
Node * rightNode2;
Node * right_maxpathNode;
int right_maxsum = maxsum root->right, right_maxpathsum, right_maxpathNode,
sumtohere+root->v, rightNode1, rightNode2);
if( root->left == NULL && root->right == NULL){
maxpathsum = sumtohere+root->v;
maxpathNode = root;
}else{
if( left_maxpathsum > right_maxpathsum){
maxpathsum = left_maxpathsum;
maxpathNode = left_maxpathNode;
}else{
maxpathsum = right_maxpathsum;
maxpathNode = right_maxpathNode;
}
}
int curmaxsum = left_maxpathsum + right_maxpathsum - root->v - sumtohere;
if( curmaxsum >= left_maxsum && curmaxsum >= right_maxsum){
n1 = left_maxpathNode;
n2 = right_maxpathNode;
return curmaxsum;
}else if( left_maxsum >= curmaxsum && left_maxsum > right_maxsum){
n1 = leftNode1;
n2 = leftNode2;
return left_maxsum;
}else{
n1 = rightNode1;
n2 = rightNode2;
return right_maxsum;
}
}
int find_max(Node * root, Node * & n1, Node * & n2){
int maxpath;
return maxsum(root,maxpath, 0, n1, n2);
}
【在 i**********e 的大作中提到】
: 你的代码没有返回两个叶子节点，题目说清楚要找这两个叶子节点。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
| d*******d
发帖数: 2050 | 36 这回应该满足要求了,不过没刚才好看了
【在 d*******d 的大作中提到】
: 这好办
: int maxsum(Node * root, int & maxpathsum, Node * & maxpathNode,
: int sumtohere, Node * & n1, Node * & n2){
: if( root== NULL){
: maxpathsum = sumtohere;
: maxpathNode = NULL;
: n1 = NULL;
: n2 = NULL;
: return 0;
: }
| B*******1
发帖数: 2454 | 37 我也觉得是这样子可以.
【在 d*******l 的大作中提到】
: 我觉得如果root==null返回负无穷的话，就不一定需要complete binary tree
| d*******l
发帖数: 338 | 38 如果没有完全二叉树这个条件，你的代码应该是有问题的，可能会把那些不存在的节点
当成值为0的叶节点，造成不符合要求。
比如：
1
-10 2
－10
【在 d*******d 的大作中提到】
: 我觉得没有这个必要,按照我上面的code,只有单孩子节点的node, 在递归中会被他的母
: 节点取代.
| d*******l
发帖数: 338 | 39 后来又想了想这样还是不行的，今天犯的错比较多。这样会影响正常的路径。
只有分情况判断一下了。
【在 B*******1 的大作中提到】
: 我也觉得是这样子可以.
| B*******1
发帖数: 2454 | 40 仔细看了一下你的code，似乎有这么个问题
譬如
a
/ \
b c
/ \ / \
d e f g
假如a的左子树b的最大值是通过b+d+e而来的，而不是b+e来的，那么你的答案就已经
set了啊，
就是说，
1.你可以用a 加上左子树一个路径+右子树一个路径
2. 你可以用a + 两个路径都来自左子树
3.你可以用a + 两个路径都来自右子树
但是你的递归，似乎是如果左子树已经选择了2个路径，还可以往右子树再选择2个路径
。
);
【在 d*******d 的大作中提到】
: 我觉得没那么复杂,
: 没试验过
: int maxsum(Node * root, int & maxpathsum, int sumtohere){
: if( root== NULL){
: maxpathsum = sumtohere;
: return 0;
: }
: int left_maxpathsum = 0;
: int left_maxsum = maxsum( root->left, left_maxpathsum, sumtohere+root->v);
: int right_maxpathsum = 0;
| | | F**r
发帖数: 84 | 41 in-order traversal
root
【在 B*******1 的大作中提到】
: Given a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is
: maximum where F(X,Y) = sum of nodes in the path from root to X + sum of
: nodes in the path from root to Y - sum of nodes in the common path from root
: to first common ancestor of the Nodes X and Y
| r*******y
发帖数: 1081 | 42 how about using two recursive funciton ?
int maxpath(node * root) retun the max sum of the nodes along the path from
root to a leaf.
int maxpath2(node * root) return max F(x, y).
Below is the implementation
int maxpath(node *root){
if (root == NULL) return 0;
if (root->left == NULL) return root.value + maxpath(root->right);
if (root->right == NULL) return root.value + maxpath(root->left);
return root.value + max(maxpath(root->left), maxpath(root->right));
}
int maxpath2(node * root){
if(root == NULL) return 0;
int p1 = maxpath(root->left);
int p2 = maxpath(root->right);
return max(p1+p2 , maxpath2(root->left), maxpath2(root->right))+root.
value;
}
but the complexity is a big deal here.
【在 B*******1 的大作中提到】
: 仔细看了一下你的code，似乎有这么个问题
: 譬如
: a
: / \
: b c
: / \ / \
: d e f g
: 假如a的左子树b的最大值是通过b+d+e而来的，而不是b+e来的，那么你的答案就已经
: set了啊，
: 就是说，
| d*******d
发帖数: 2050 | 43 nod nod,
you are right
【在 d*******l 的大作中提到】
: 如果没有完全二叉树这个条件，你的代码应该是有问题的，可能会把那些不存在的节点
: 当成值为0的叶节点，造成不符合要求。
: 比如：
: 1
: -10 2
: －10
| d*******l
发帖数: 338 | 44 他的left_maxpathsum和left_maxsum是不一样的。最开始他的版本好像是有这个问题，
不过他很快修改过来，现在倒是没有这个问题。
【在 B*******1 的大作中提到】
: 仔细看了一下你的code，似乎有这么个问题
: 譬如
: a
: / \
: b c
: / \ / \
: d e f g
: 假如a的左子树b的最大值是通过b+d+e而来的，而不是b+e来的，那么你的答案就已经
: set了啊，
: 就是说，
| i*****f
发帖数: 578 | 45 题目看错了。。。以为是最大化node个数。。。
这里是新的解，借鉴了wwwar3的解，而且应该可以handle树不complete的情况。牛牛们
看看还有什么为题没有？（测试及测试结果在最后面）
'''
Tree node is a 3-tuple (value, left child, right child)
'''
D = {}
def MaxPathSum(N):
'''
Find the path from N to a leaf that maximize the sum from N to the leaf.
Returns [leaf, sum]
'''
assert N!=None
if D.has_key(N): return D[N]
if not N[1] and not N[2]: return [N, N[0]]
r = [None, float('-inf')]
if N[1]:
r = MaxPathSum(N[1])
if N[2]:
r = max(r, MaxPathSum(N[2]), key=lambda x:x[1])
r[1] += N[0]
D[N] = r
return r
def MaxF(R):
'''Find leaf nodes X,Y that maximize F(X,Y).
Returns (X,Y,max_v).
'''
if not R[1] and not R[2]: return [R,R,R[0]]
res = [None,None,float('-inf')]
res1 = MaxF(R[1]) if R[1] else None
res2 = MaxF(R[2]) if R[2] else None
if res1 and res2:
res1[2] += R[0]
res2[2] += R[0]
t1 = MaxPathSum(R[1])
t2 = MaxPathSum(R[2])
res3 = [t1[0], t2[0], t1[1]+t2[1]+R[0]]
return max(res1,res2,res3, key=lambda x:x[2])
n = R[1] or R[2]
res = MaxF(n)
res[2] += R[0]
return res
########## tests ###########
# test:
R = (1,
(2,
(4,None,None),
(5,
None,
(9,None,None))),
(-9,
(6,None,None),
(7,
(8,None,None),
None)))
# linked list
R2 = (1,
None,
(2,
None,
(3,
None,
None,)))
print MaxF(R)
print MaxF(R2)
测试结果：
[(9, None, None), (8, None, None), 23]
[(3, None, None), (3, None, None), 6]
【在 i*****f 的大作中提到】
: Good recursion. But looks not exactly what lz asked - X,Y has to be leaf. In
: your case what if root only has one child? It measures the distance from
: root to deepest child in the right subtree?
| d*******d
发帖数: 2050 | 46 还是有问题,现在又改了改
【在 d*******l 的大作中提到】
: 他的left_maxpathsum和left_maxsum是不一样的。最开始他的版本好像是有这个问题，
: 不过他很快修改过来，现在倒是没有这个问题。
| w*****3
发帖数: 101 | 47 我开始理解错了，
这个思路基本上是darksteel 说的一样，
java返回多个参数还真不方便，
HashMap map = new HashMap();
btn ln = null, rn = null;
int max = 0;
/*
* find the maximum pair
*/
public void solve(btn root) {
if (root == null)
return;
maxValue(root);
go(root, 0);
print(ln.value);
print(rn.value);
}
/*
* for each node, find the maximum pair
*/
private void go(btn root, int sumhere) {
if (root.left == null || root.right == null) {
return;
}
item left = map.get(root.left);
item right = map.get(root.right);
if (left.value + right.value + sumhere + root.value > max) {
max = left.value + right.value + sumhere + root.value;
ln = left.node;
rn = right.node;
}
go(root.left, sumhere + root.value);
go(root.right, sumhere + root.value);
}
/*
* find the biggest value and the leaf node from a node
* and store them in a hashmap
*/
public item maxValue(btn root) {
item tmpitem = null;
if (root.left == null && root.right == null) {
tmpitem = new item(root.value, root);
map.put(root, tmpitem);
return tmpitem;
}
if (map.containsKey(root))
return map.get(root);
item li = maxValue(root.left);
item ri = maxValue(root.right);
if (li.value > ri.value) {
tmpitem = new item(li.value + root.value, li.node);
} else {
tmpitem = new item(ri.value + root.value, ri.node);
}
map.put(root, tmpitem);
return tmpitem;
}
class item {
public item(int i, btn root) {
value = i;
node = root;
}
int value;
btn node;
} | B*******1
发帖数: 2454 | 48 帮忙看看我的code能否处理一个孩子的情况？
测试树：
8
/ \
/ \
/ \
/ \
/ \
0 14
/ \ / \
/ \ / \
/ \ 11 5
17 24 \ \
\ / \ 12 45
34 / \
19 28
答案: 28 和 45
最大和124
typedef pair Item;
Item MaxpathSum(Tree *node, int &CurMaxSum, int SumToNow, Tree *&ln, Tree *&rn)
{
if (node->left && !node->right) {
Item leftPathMax = MaxpathSum(node->left, CurMaxSum, SumToNow+node->element, ln, rn);
return Item(node->element+node->left->element, leftPathMax.second);
} else if (node->right && !node->left) {
Item rightPathMax = MaxpathSum(node->right, CurMaxSum, SumToNow+node->element, ln, rn);
return Item(node->element+node->right->element, rightPathMax.second);
} else if (!node->left && !node->right) {
return Item(node->element, node);
}
Item leftPathMax = MaxpathSum(node->left, CurMaxSum, SumToNow+node->element, ln, rn);
Item rightPathMax = MaxpathSum(node->right, CurMaxSum, SumToNow+node->element, ln, rn);
int MaxSum = leftPathMax.first + node->element + rightPathMax.first + SumToNow;
cout << MaxSum << endl;
if (MaxSum > CurMaxSum) {
CurMaxSum = MaxSum;
ln = leftPathMax.second;
rn = rightPathMax.second;
}
return leftPathMax.first > rightPathMax.first ?
Item(leftPathMax.first+node->element, leftPathMax.second):
Item(rightPathMax.first+node->element, rightPathMax.second);
}
void Find_Max_Pair(Tree *root)
{
int MaxSum = INT_MIN;
int CurMaxSum = INT_MIN;
int SumToNow = 0;
Tree *ln;
Tree *rn;
Item test = MaxpathSum2(root, MaxSum, SumToNow, ln, rn);
return;
} | g**********y
发帖数: 14569 | 49 针对完全二叉树，写了一个O(N)的DP version, 自底向上计算，一次扫描完成。
- 因为是完全二叉树，节点值保存在数组a里，N = 2^k-1
- 这个version可以计算负数的情况。
- low[i]: 节点i的第二最佳路径, individual部分
- high[i]: 节点i的最佳路径，individual部分
- common[i]：节点i的两条最佳路径公共部分
public int F(int[] a) {
int N = a.length;
int[] low = new int[N];
int[] high = new int[N];
int[] common = new int[N];
for (int i = N - 1; i >= N / 2; i--) {
high[i] = a[i];
low[i] = Integer.MIN_VALUE;
}
for (int i = N / 2 - 1; i >= 0; i--) {
int left = i * 2 + 1;
int right = i * 2 + 2;
int s = high[left]+common[left] > high[right]+common[right] ?
left : right;
int t = high[left]+common[left] > high[right]+common[right] ?
right : left;
if (low[s] > high[t] + common[t]) {
low[i] = low[s];
high[i] = high[s];
common[i] = common[s] + a[i];
} else {
low[i] = high[t] + common[t];
high[i] = high[s] + common[s];
common[i] = a[i];
}
}
return low[0] + high[0] + common[0];
} | t******g
发帖数: 252 | 50 Is it o(n) or O(n)?
【在 B*******1 的大作中提到】
: 谢谢大家的回答，补充，这个tree是complete binary tree， 最佳算法是o(n)的。
| | | r******l
发帖数: 10760 | 51 “节点i的最佳路径”什么意思？
【在 g**********y 的大作中提到】
: 针对完全二叉树，写了一个O(N)的DP version, 自底向上计算，一次扫描完成。
: - 因为是完全二叉树，节点值保存在数组a里，N = 2^k-1
: - 这个version可以计算负数的情况。
: - low[i]: 节点i的第二最佳路径, individual部分
: - high[i]: 节点i的最佳路径，individual部分
: - common[i]：节点i的两条最佳路径公共部分
: public int F(int[] a) {
: int N = a.length;
: int[] low = new int[N];
: int[] high = new int[N];
| r******l
发帖数: 10760 | 52 你这个程序里面，叶子节点的commen都没赋值就直接拿来用？
【在 g**********y 的大作中提到】
: 针对完全二叉树，写了一个O(N)的DP version, 自底向上计算，一次扫描完成。
: - 因为是完全二叉树，节点值保存在数组a里，N = 2^k-1
: - 这个version可以计算负数的情况。
: - low[i]: 节点i的第二最佳路径, individual部分
: - high[i]: 节点i的最佳路径，individual部分
: - common[i]：节点i的两条最佳路径公共部分
: public int F(int[] a) {
: int N = a.length;
: int[] low = new int[N];
: int[] high = new int[N];
| g**********y
发帖数: 14569 | 53 1. Java default 0
2. 节点最佳路径，从该节点出发，到叶子的最大路径值。
【在 r******l 的大作中提到】
: 你这个程序里面，叶子节点的commen都没赋值就直接拿来用？
| r******l
发帖数: 10760 | 54 嗯，其实最佳路径容易理解，主要是你那个“第二最佳”不容易理解。
节点最佳路径，从该节点出发，到叶子的最大路径值。这样定义下，你那个“第二最佳
”其实并不是“从该节点出发，到叶子的第二大路径值”，而是“从该节点出发，到跟
最佳路径组合起来总和最大的那个叶子节点的路径值”。说起来可能比较别扭，不过程
序应该对。
完全二叉树很容易从下往上倒着遍历。你这个程序能否推广到处理任意二叉树呢？
另外，原题要求输出那两个叶子节点，不是最大值。你还应该把他们也记下来。
【在 g**********y 的大作中提到】
: 1. Java default 0
: 2. 节点最佳路径，从该节点出发，到叶子的最大路径值。
| g**********y
发帖数: 14569 | 55 输出两个叶子节点，改一下数据结构就行。
任意二叉树比较麻烦，我不知道有什么简单的办法可以自底向上一层一层地遍历。
【在 r******l 的大作中提到】
: 嗯，其实最佳路径容易理解，主要是你那个“第二最佳”不容易理解。
: 节点最佳路径，从该节点出发，到叶子的最大路径值。这样定义下，你那个“第二最佳
: ”其实并不是“从该节点出发，到叶子的第二大路径值”，而是“从该节点出发，到跟
: 最佳路径组合起来总和最大的那个叶子节点的路径值”。说起来可能比较别扭，不过程
: 序应该对。
: 完全二叉树很容易从下往上倒着遍历。你这个程序能否推广到处理任意二叉树呢？
: 另外，原题要求输出那两个叶子节点，不是最大值。你还应该把他们也记下来。
|
|
