输入一个二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

如上图的二叉树，当输入根结点和一个数值12的时候，就有两条路径“1->2->4->5”和“1->3->8”，如果存在，就输出上述路径，如果没有任何一条路径满足就不输出路径并提示；

首先，路径一定是从根结点开始到某个叶子结点结束，这才是一条路径，因此，应该最先访问的就是根结点，而在二叉树的先中后序遍历中只有先序遍历是最先访根结点的，所以可以用如下方法：用先序遍历方法遍历二叉树，每当经过一个结点的时候就将其值进行保存相加，如果中途发现或者到达叶子结点之后，当前路径相加得到的值并不满足要求的值，则往回退并将值减去，或者当前路径已经满足，则需要再去换一条路径访问看是否还有其他路径满足条件，而能够提供往回退的方法就只有递归了，直至遍历完毕二叉树；


程序设计如下：

#include<iostream>#include<assert.h>#include<vector>usingnamespacestd;structBinaryTreeNode//二叉树结点数据结构{int_val;BinaryTreeNode*_Lnode;BinaryTreeNode*_Rnode;BinaryTreeNode(intval):_val(val),_Lnode(NULL),_Rnode(NULL){}};BinaryTreeNode*_Create(int*arr,size_t&index,size_tsize)//创建二叉树{if((index<size)&&(arr[index]!='#')){BinaryTreeNode*root=newBinaryTreeNode(arr[index]);root->_Lnode=_Create(arr,++index,size);root->_Rnode=_Create(arr,++index,size);returnroot;}elsereturnNULL;}BinaryTreeNode*CreateBinaryTree(int*arr,size_tsize){assert(arr&&size);size_tindex=0;return_Create(arr,index,size);}voidDestoryBinaryTree(BinaryTreeNode*root)//销毁二叉树{if(root!=NULL){DestoryBinaryTree(root->_Lnode);DestoryBinaryTree(root->_Rnode);deleteroot;}}voidPrevOrder(BinaryTreeNode*root)//前序遍历打印出二叉树{if(root!=NULL){cout<<root->_val<<"";PrevOrder(root->_Lnode);PrevOrder(root->_Rnode);}}void_Count(BinaryTreeNode*root,vector<int>*pv,int&count,intnum){if(root!=NULL){count+=root->_val;//每当一个结点不为NULL的时候，就将其放入容器中且加上其值(*pv).push_back(root->_val);_Count(root->_Lnode,pv,count,num);_Count(root->_Rnode,pv,count,num);if(count==num)//当找到一个路径的时候就将其打印出来{cout<<"APathIs:";for(size_ti=0;i<(*pv).size();++i)cout<<(*pv)[i]<<"->";cout<<"NULL"<<endl;}count-=(*pv).back();//退回上一步(*pv).pop_back();}}voidPrintPathOfNumInBT(BinaryTreeNode*root,intnum)//打印路径{assert(root);vector<int>v;//用一个容器来存放路径intcount=0;//用一个计数器计算和_Count(root,&v,count,num);}intmain(){intarr[]={1,2,6,'#','#',4,5,'#','#','#',3,7,'#','#',8,'#','#'};intnum=12;BinaryTreeNode*root=CreateBinaryTree(arr,sizeof(arr)/sizeof(arr[0]));cout<<"PrevOrder:";PrevOrder(root);cout<<endl;PrintPathOfNumInBT(root,num);DestoryBinaryTree(root);return0;}


运行程序：



《完》