S**I
发帖数: 15689 | 1 ☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Tue Jun 21 01:52:31 2011, 美东) 提到:
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
☆─────────────────────────────────────☆
SecretVest (Secret Vest) 于 (Tue Jun 21 04:01:30 2011, 美东) 提到:
not hard if someone is used to thinking recursively.
root
☆─────────────────────────────────────☆
icewolf (好好活) 于 (Tue Jun 21 10:51:24 2011, 美东) 提到:
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?
☆─────────────────────────────────────☆
timzheng (zmit) 于 (Tue Jun 21 10:56:17 2011, 美东) 提到:
Everything is zero.
☆─────────────────────────────────────☆
timzheng (zmit) 于 (Tue Jun 21 11:06:32 2011, 美东) 提到:
Never mind.
☆─────────────────────────────────────☆
gloomyturkey (一只郁闷的火鸡) 于 (Tue Jun 21 11:07:05 2011, 美东) 提到:
这个code假定X, Y分属root的左右子树？
☆─────────────────────────────────────☆
timzheng (zmit) 于 (Tue Jun 21 11:11:00 2011, 美东) 提到:
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.
☆─────────────────────────────────────☆
timzheng (zmit) 于 (Tue Jun 21 11:15:21 2011, 美东) 提到:
I would also asking questions to clarify the problem.
Can X, Y be the same node?
☆─────────────────────────────────────☆
gloomyturkey (一只郁闷的火鸡) 于 (Tue Jun 21 11:20:51 2011, 美东) 提到:
Basically, need another function like:
public int G(bn root) {
return max(F(root), root.value + G(root.left), root.value + G(root.right
));
}
☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Tue Jun 21 12:00:45 2011, 美东) 提到:
谢谢大家的回答，补充，这个tree是complete binary tree， 最佳算法是o(n)的。
☆─────────────────────────────────────☆
darksteel (darksteel) 于 (Tue Jun 21 13:23:12 2011, 美东) 提到:
对于每个非叶节点，算出对应的maxValue，这个可以O(n)做到。
对于每个非叶节点，用maxValue(leftChild)+maxValue(rightChild)去更新当前最大值
。也可以O(n)做到。
其实本质上就是wwwwar3的方法，保存每个节点的maxValue用到hashmap，如果是完全二
叉树也可以考虑用数组，那这个问题就非常像DP了。
wwwwar3的方法中对于null返回0感觉值得商榷，如果认为X和Y可以是同一个节点那可以
这么做，否则返回负无穷比较合适。
☆─────────────────────────────────────☆
AFGHM (IT companies) 于 (Tue Jun 21 13:34:19 2011, 美东) 提到:
我想到的一个办法是比较简单的递归：
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;
}
☆─────────────────────────────────────☆
darksteel (darksteel) 于 (Tue Jun 21 13:49:39 2011, 美东) 提到:
方法应该是对的，但为什么要加SumFromRoot呢？题目中的要求应该是要减去这一部分
的啊。
☆─────────────────────────────────────☆
ihasleetcode (1337coder) 于 (Tue Jun 21 13:51:01 2011, 美东) 提到:
你的基本思路是对的，但是：
1)问题要得到两个叶子节点，不单单只是 maxsum
2)你的代码 assume 所有节点值都是正数
稍微更改一下就好了。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
☆─────────────────────────────────────☆
ihasleetcode (1337coder) 于 (Tue Jun 21 13:52:11 2011, 美东) 提到:
刚才写的，没有验证过。。。
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
☆─────────────────────────────────────☆
AFGHM (IT companies) 于 (Tue Jun 21 13:53:26 2011, 美东) 提到:
从题目要求看， SumFromRoot 加两次， 然后又减一次， 其实相当于加一次。
☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Tue Jun 21 13:57:55 2011, 美东) 提到:
对的,我就是看了你之前的人的解答,全部人都没有加这一部分...
☆─────────────────────────────────────☆
darksteel (darksteel) 于 (Tue Jun 21 14:01:25 2011, 美东) 提到:
额，确实，先入为主了，还是不够仔细。
☆─────────────────────────────────────☆
AFGHM (IT companies) 于 (Tue Jun 21 14:02:22 2011, 美东) 提到:
1)恩。 是需要改一下。加个参数返回值就可以了
2） 这个我倒没考虑呢。
☆─────────────────────────────────────☆
darksteel (darksteel) 于 (Tue Jun 21 14:05:12 2011, 美东) 提到:
没错，还是题目没看清楚，最开始我甚至以为是路径上的节点数目的和。。这样的话，
似乎只要像ihasleetcode说的那样，解决下节点值为负数的情况就可以了，在参数里再
加个值应该就行。
☆─────────────────────────────────────☆
ihasleetcode (1337coder) 于 (Tue Jun 21 14:07:55 2011, 美东) 提到:
第二点我看错了，你的代码是对的，可以返回正确的 maxsum.
关于第一点，我一开始也是跟你一样，base case 判断为 NULL == root。这个如果只
是返回 maxsum 没有问题，但是如果要返回两个叶子节点的话就应该更改下 base case.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Tue Jun 21 14:08:20 2011, 美东) 提到:
我看了好久他之前的帖子的code，就是没有看到code里面有加这部分node的和的操作。
☆─────────────────────────────────────☆
dinohound (dino) 于 (Tue Jun 21 14:21:43 2011, 美东) 提到:
我觉得没那么复杂,
没试验过
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
☆─────────────────────────────────────☆
ihasleetcode (1337coder) 于 (Tue Jun 21 14:24:04 2011, 美东) 提到:
还有一点，这题假设 binary tree 是 complete 是有原因的。
complete binary tree 可以保证每个节点必须有０个或者２个孩子。
这样可以保证每个递归都可以有两个 leaf node，也就是一个 solution candidate。
然后再比较两个 leaf node，返回那个路径比较大的给 parent。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
☆─────────────────────────────────────☆
dinohound (dino) 于 (Tue Jun 21 14:28:03 2011, 美东) 提到:
我觉得没有这个必要,按照我上面的code,只有单孩子节点的node, 在递归中会被他的母
节点取代.
☆─────────────────────────────────────☆
ihasleetcode (1337coder) 于 (Tue Jun 21 14:29:34 2011, 美东) 提到:
你的代码没有返回两个叶子节点，题目说清楚要找这两个叶子节点。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
☆─────────────────────────────────────☆
AFGHM (IT companies) 于 (Tue Jun 21 14:33:21 2011, 美东) 提到:
我也没考虑complete binary tree的因素。
return的 maxsum 是有问题的， 正确的应该是
当前节点的MaxSum = max( CurSumFromRoot + LMaxSumToLeaf + RMaxSumToLeaf,
左节点的maxsum,
右节点的maxsum)
☆─────────────────────────────────────☆
darksteel (darksteel) 于 (Tue Jun 21 14:33:47 2011, 美东) 提到:
恩，居然大家都没注意到。上面想法一度有些混乱，总结一下，这题可以用递归做，每
个节点的maxsum依赖于3部分，一部分是根节点到它的sum，还有就是它左右子树向下的
最大path的sum，所以参数中要保存根节点到当前的sum，递归的过程中，在向下推的时
候是把这一部分求出来，向上收的时候是计算向下path的最大sum并且更新最大值。这
样应该没错了。
☆─────────────────────────────────────☆
darksteel (darksteel) 于 (Tue Jun 21 14:41:27 2011, 美东) 提到:
我觉得如果root==null返回负无穷的话，就不一定需要complete binary tree
☆─────────────────────────────────────☆
ihasleetcode (1337coder) 于 (Tue Jun 21 14:47:14 2011, 美东) 提到:
是的，你是对的。
只有单孩子节点的话，那其中一个 lChild or rChild 的 sum 会为０。
但是如果不只是要返回 maxsum，而也返回两个叶子节点的话就要额外判断了。
你的代码是很简洁，但是我说过了，没有达到题目的要求。
题目要求的是返回两个叶子节点，这个你代码不能轻易解决。不是简单地加入额外的两
个返回值就可以了。
☆─────────────────────────────────────☆
dinohound (dino) 于 (Tue Jun 21 14:48:13 2011, 美东) 提到:
这好办
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);
}
☆─────────────────────────────────────☆
dinohound (dino) 于 (Tue Jun 21 14:50:28 2011, 美东) 提到:
这回应该满足要求了,不过没刚才好看了
☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Tue Jun 21 15:36:14 2011, 美东) 提到:
我也觉得是这样子可以.
☆─────────────────────────────────────☆
darksteel (darksteel) 于 (Tue Jun 21 16:04:14 2011, 美东) 提到:
如果没有完全二叉树这个条件，你的代码应该是有问题的，可能会把那些不存在的节点
当成值为0的叶节点，造成不符合要求。
比如：
1
-10 2
－10
☆─────────────────────────────────────☆
darksteel (darksteel) 于 (Tue Jun 21 16:06:56 2011, 美东) 提到:
后来又想了想这样还是不行的，今天犯的错比较多。这样会影响正常的路径。
只有分情况判断一下了。
☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Tue Jun 21 16:48:05 2011, 美东) 提到:
仔细看了一下你的code，似乎有这么个问题
譬如
a
/ \
b c
/ \ / \
d e f g
假如a的左子树b的最大值是通过b+d+e而来的，而不是b+e来的，那么你的答案就已经
set了啊，
就是说，
1.你可以用a 加上左子树一个路径+右子树一个路径
2. 你可以用a + 两个路径都来自左子树
3.你可以用a + 两个路径都来自右子树
但是你的递归，似乎是如果左子树已经选择了2个路径，还可以往右子树再选择2个路径
。
);
☆─────────────────────────────────────☆
FCer (FCer) 于 (Tue Jun 21 16:52:20 2011, 美东) 提到:
in-order traversal
root
☆─────────────────────────────────────☆
romancity (山顶一枝草) 于 (Tue Jun 21 16:54:25 2011, 美东) 提到:
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.
☆─────────────────────────────────────☆
dinohound (dino) 于 (Tue Jun 21 16:59:45 2011, 美东) 提到:
nod nod,
you are right
☆─────────────────────────────────────☆
darksteel (darksteel) 于 (Tue Jun 21 17:02:48 2011, 美东) 提到:
他的left_maxpathsum和left_maxsum是不一样的。最开始他的版本好像是有这个问题，
不过他很快修改过来，现在倒是没有这个问题。
☆─────────────────────────────────────☆
icewolf (好好活) 于 (Tue Jun 21 17:12:43 2011, 美东) 提到:
题目看错了。。。以为是最大化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]
☆─────────────────────────────────────☆
dinohound (dino) 于 (Tue Jun 21 17:22:21 2011, 美东) 提到:
还是有问题,现在又改了改
☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Tue Jun 21 23:28:47 2011, 美东) 提到:
帮忙看看我的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;
}
☆─────────────────────────────────────☆
gloomyturkey (一只郁闷的火鸡) 于 (Wed Jun 22 09:52:25 2011, 美东) 提到:
针对完全二叉树，写了一个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];
}
☆─────────────────────────────────────☆
timzheng (zmit) 于 (Wed Jun 22 10:46:33 2011, 美东) 提到:
Is it o(n) or O(n)?
☆─────────────────────────────────────☆
redpearl (redpearl) 于 (Wed Jun 22 14:07:00 2011, 美东) 提到:
“节点i的最佳路径”什么意思？
☆─────────────────────────────────────☆
redpearl (redpearl) 于 (Wed Jun 22 14:12:34 2011, 美东) 提到:
你这个程序里面，叶子节点的commen都没赋值就直接拿来用？
☆─────────────────────────────────────☆
gloomyturkey (一只郁闷的火鸡) 于 (Wed Jun 22 14:19:05 2011, 美东) 提到:
1. Java default 0
2. 节点最佳路径，从该节点出发，到叶子的最大路径值。
☆─────────────────────────────────────☆
redpearl (redpearl) 于 (Wed Jun 22 14:43:09 2011, 美东) 提到:
嗯，其实最佳路径容易理解，主要是你那个“第二最佳”不容易理解。
节点最佳路径，从该节点出发，到叶子的最大路径值。这样定义下，你那个“第二最佳
”其实并不是“从该节点出发，到叶子的第二大路径值”，而是“从该节点出发，到跟
最佳路径组合起来总和最大的那个叶子节点的路径值”。说起来可能比较别扭，不过程
序应该对。
完全二叉树很容易从下往上倒着遍历。你这个程序能否推广到处理任意二叉树呢？
另外，原题要求输出那两个叶子节点，不是最大值。你还应该把他们也记下来。
☆─────────────────────────────────────☆
gloomyturkey (一只郁闷的火鸡) 于 (Wed Jun 22 15:02:04 2011, 美东) 提到:
输出两个叶子节点，改一下数据结构就行。
任意二叉树比较麻烦，我不知道有什么简单的办法可以自底向上一层一层地遍历。 |
|
