1 #include <iostream> 2 #include <vector> 3 #include <stdlib.h> 4 /* 5     题目：在二元树中找出和为某一值的所有路径 6  7 输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。 8 打印出和与输入整数相等的所有路径。 9 例如输入整数22 和如下二元树10           1011         / 12        5  1213       / 14      4   715 则打印出两条路径：10, 12 和10, 5, 7。16 17 */18 using namespace std;19 struct BinaryTree20 {21     int m_nValue;22     BinaryTree* m_left;23     BinaryTree* m_right;24 };25 void addTree(BinaryTree **T,int num) //创建二元树26 {27     if(*T==NULL)28     {29         *T=(BinaryTree*)malloc(sizeof(BinaryTree));30         (*T)->m_nValue=http://www.mamicode.com/num;31         (*T)->m_left=NULL;32         (*T)->m_right=NULL;33     }34     else if((*T)->m_nValue>num)35     {36         addTree(&((*T)->m_left),num);37     }38      else if((*T)->m_nValue<num)39     {40         addTree(&((*T)->m_right),num);41     }42     else43     {44         cout<<"重复加入同一节点"<<endl;45     }46 }47 /*48     expect存放期望值，path存放二元树的节点，curSum存放搜索到当前节点的值49 50 */51 void findPath(BinaryTree* pTree,int expect,vector<int> &path,int& curSum)52 {53     if(!pTree)54     return;55     curSum+=pTree->m_nValue;  //把当前节点的值加到总和值中56     path.push_back(pTree->m_nValue);  //并把它存放到vector中57     bool isLeaf=!(pTree->m_left)&&!(pTree->m_right); //判断是否到了叶子结点58     if(expect==curSum && isLeaf) //如果总和值刚好等于期望值还有就是搜索到了叶子结点59     {60         vector<int>::iterator it; //打印出该路径的值61         for(it=path.begin();it!=path.end();it++)62         {63             cout<<*it<<"\t";64         }65         cout<<endl;66     }67     if(pTree->m_left) //如果还有左子节点则继续搜索68     {69         findPath(pTree->m_left,expect,path,curSum);70     }71     if(pTree->m_right)//如果还有右子节点则继续搜索72     {73         findPath(pTree->m_right,expect,path,curSum);74     }75     curSum-=pTree->m_nValue; //如果到了叶子结点还没有找到期望值或者当前总和超过了期望值76     path.pop_back(); //则减去该节点值，并把该节点从vector中删除77 }78 79 int main()80 {81     BinaryTree* T =NULL;82     addTree(&T,10);83     addTree(&T,12);84     addTree(&T,5);85     addTree(&T,7);86     addTree(&T,4);87     vector<int> path;88     int sum=0;89     findPath(T,22,path,sum);90     cout<<sum;91     return 0;92 }