c**y
发帖数: 172 | 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**********s
发帖数: 441 | |
f*********5
发帖数: 576 | 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********5
发帖数: 715 | 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**y
发帖数: 172 | 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;}
: }
: }
|
