a question regarding finding all paths with a common sum - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

a question regarding finding all paths with a common sum

a question regarding finding all paths with a common sum# JobHunting - 待字闺中

c*y2010-07-22 07:07

1 楼

问题是找到一个binary tree中所有路径，对于每一条这样得路径，其成员节点的和等
于一个指定的值。附带的说明是符合条件的路径不是必须从root开始。下面是
CareerCup的问题说明和解答。
我的疑惑是这个solution给出的路径（们）确实可以不是从root开始，但是每一条路径
一定是沿着root到某一个叶子节点（即在较低level的端点一定是在一个以在较高level
端点为顶点的subtree里面），而不会出现路径的两端出现在两个不同的subtree中。
However，题的说明之中并没有指明路径的两端不可以出现在两个不同的subtree中。
如何修改下面的solution使得上面所说的路径可以被找到呢？Thanks
Problem:
You are given a binary tree in which each node contains a value. Design an
algorithm to print all paths which sum up to that value. Note that it can be
any path in the tree

I*s2010-07-22 07:07

2 楼

我一直觉得这不是subset sum问题吗? 是NPC的. 作为面试是不是难了点?
http://en.wikipedia.org/wiki/Subset_sum_problem

f*52010-07-22 07:07

3 楼

void GetPath(node * root, vector&vec,int target)
{
if(!root) return;
if(vec.size()>0)
{ sum=0;
for(int i=vec.size()-1;i>=0;i--)
{ sum+=vec[i];
if(sum==target) { PRINT;break;}
}
}
vec.push_back(root->data);
if (root->left) GetPath(root->left,vec,target);
if (root->right) GetPath(root->right,vec,target);
return;
}

level
Design an

【在 c**y 的大作中提到】

: 问题是找到一个binary tree中所有路径，对于每一条这样得路径，其成员节点的和等
: 于一个指定的值。附带的说明是符合条件的路径不是必须从root开始。下面是
: CareerCup的问题说明和解答。
: 我的疑惑是这个solution给出的路径（们）确实可以不是从root开始，但是每一条路径
: 一定是沿着root到某一个叶子节点（即在较低level的端点一定是在一个以在较高level
: 端点为顶点的subtree里面），而不会出现路径的两端出现在两个不同的subtree中。
: However，题的说明之中并没有指明路径的两端不可以出现在两个不同的subtree中。
: 如何修改下面的solution使得上面所说的路径可以被找到呢？Thanks
: Problem:
: You are given a binary tree in which each node contains a value. Design an

M*52010-07-22 07:07

4 楼

呵呵，对头，这题用的就是recursion

【在 f*********5 的大作中提到】

: void GetPath(node * root, vector&vec,int target)
: {
: if(!root) return;
: if(vec.size()>0)
: { sum=0;
: for(int i=vec.size()-1;i>=0;i--)
: { sum+=vec[i];
: if(sum==target) { PRINT;break;}
: }
: }

c*y2010-07-22 07:07

5 楼

Thanks for your solution. Yours is the same as the solution given in
CareerCup. So it shares the same problem as mentioned above, that is, it
only finds all paths such that one end must be in a subtree with the other
end as root. Can your solution find other paths in which two ends are cross
different subtrees? I will appreciate you very much if you could clarify an
answer for that case. Many thanks ahead.

【在 f*********5 的大作中提到】

: void GetPath(node * root, vector&vec,int target)
: {
: if(!root) return;
: if(vec.size()>0)
: { sum=0;
: for(int i=vec.size()-1;i>=0;i--)
: { sum+=vec[i];
: if(sum==target) { PRINT;break;}
: }
: }