从根到树叶, 找出所有路径中 和为给定的路径。
先序遍历,把访问到的节点放入vector中。当递归返回时从vector中删除节点。
参考代码:
#include<iostream>
#include<vector>
using namespace std;
struct Tree
{
Tree(int num):element(num),left(NULL),right(NULL){}
int element;
Tree* left;
Tree* right;
};
Tree* init()
{
Tree *root = new Tree(10);
root->left = new Tree(5);
root->right = new Tree(12);
root->left->left = new Tree(4);
root->left->right = new Tree(7);
return root;
}
vector<Tree> node;
void find( Tree *r, int sum)
{
if(r)
{
node.push_back(*r);
}
if( r->left==NULL && r->right==NULL)
{
if(sum - r->element ==0)
{
vector<Tree>::iterator i= node.begin();
for(i; i!=node.end();i++)
cout<<i->element<<" ";
cout<<endl;
}
node.erase(node.end()-1);
}
else
{
if(r->left)
{
find(r->left, sum - r->element);
}
if(r->right)
{
find(r->right, sum- r->element);
}
node.erase(node.end()-1);
}
}
int main()
{
Tree* root = init();
find(root, 22);
return 0;
}