二叉树和等于某值路径 (10 分)
已知二叉树结点为不等于0的整数。给定一个整数K，请编写程序找出以根结点为起点叶结点为终点的所有路径中，结点值之和等于K的所有路径。例如K=15，对于下图所示的二叉树t，满足条件的路径有2条，即8-5-2和8-7。若没有满足条件的路径，则亦能识别。
输入格式:
输入为2行，第一行为一组用空格间隔的整数，个数不超过100个，表示带空指针信息的二叉树先根序列，其中空指针信息用0表示。第2行为整数K。
输出格式:
输出第一行为一个整数，表示满足条件的路径条数；若没有满足条件的路径，则输出0。从第二行开始，每行为一条满足条件的路径，若有多条满足条件的路径，则按从左到右的顺序依次输出，路径中每个结点值后一个空格，若两条不同的路径包含的各结点值恰好相等，则都需输出。
输入样例1:
8 5 1 0 0 2 0 0 7 0 0
15
输出样例1:
2
8 5 2
8 7
输入样例2:
-1 2 0 0 3 0 0
2
输出样例2:
1
-1 3
输入样例3:
1 1 0 0 1 0 0
2
输出样例3:
2
1 1
1 1
输入样例4:
-1 2 0 0 3 0 0
8
输出样例4:
0
#include<bits/stdc++.h>
using namespace std;
typedef struct Node{
int val;
struct Node* l;
struct Node* r;
Node(int x):val(x),l(NULL),r(NULL){};
}Tnode,*Tree;
Tree build(Tree T)
{
int x;
scanf("%d",&x);
if(x==0){
return NULL;
}
else{
T=new Node(x);
T->l=build(T->l);
T->r=build(T->r);
}
return T;
}
vector<int> v;
vector<vector<int> > ans;
void Find(Tree T,int sum)
{
if(!T) return ;
sum=sum-T->val;//尝试这个值
v.push_back(T->val); //放进去
if(!T->l&& !T->r && !sum){ //走到叶子节点了，并且sum==0，证明这条路径能筹成 sum这个数
ans.push_back(v); //把这个解法装进去
}
else{
Find(T->l,sum); //往左子树走，
Find(T->r,sum);//往右子树走
}
v.pop_back(); //放出前面那个点，回溯
}
int main()
{
int sum;
Tree T;
T=build(T);
cin>>sum; //这个给定的总和
Find(T,sum);
cout<<ans.size()<<endl;
for(auto p:ans){
for(auto j:p){
printf("%d ",j);
}
printf("\n");
}
}
