题目描述
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct TreeNode{
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
};
void dpcTree(vector<vector<int> > &vec2,vector<int> &vec1,TreeNode *T,int &expectNumber){
if(T!=NULL){
vec1.push_back(T->val);
if(T->left!=NULL||T->right!=NULL){
dpcTree(vec2,vec1,T->left,expectNumber);
dpcTree(vec2,vec1,T->right,expectNumber);
}else{
int sum=0;
for(int i=0;i<vec1.size();i++)
sum+=vec1[i];
if(sum==expectNumber)
vec2.push_back(vec1);
}
vec1.pop_back();
}
}
vector<vector<int> > FindPath(TreeNode* root,int expectNumber){
vector<vector<int> > vec2;
vector<int> vec1;
dpcTree(vec2,vec1,root,expectNumber);
return vec2;
}
int main(){
TreeNode n1(1),n2(2),n3(3),n4(4),n5(5),n6(4),n7(7);
TreeNode *root=&n1;
n1.left=&n2;
n1.right=&n3;
n2.left=&n4;
n2.right=&n5;
n3.left=&n6;
n3.right=&n7;
FindPath(root,8);
system("pause");
}