首页 > 代码库 > 打印二叉树中和为某一值的路径

打印二叉树中和为某一值的路径

输入一个二叉树,查找该树的所有路径(从根结点到叶结点的通路),并返回和(路径上所有结点值的和)为某一指定值的路径。

 1 /////////////二叉树中和为某一值的路径/////////////////////
 2 void FindPath(BinaryTreeNode* pRoot ,int expectedSum ,vector<int>& path ,int currentSum)
 3 {
 4     if (pRoot == NULL)
 5     {
 6         return;
 7     }
 8     currentSum += pRoot->m_nValue;
 9     path.push_back(pRoot->m_nValue);
10     //如果是叶子结点,且结点的和等于希望的值,打印出这条路径
11     if (currentSum == expectedSum && pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL)
12     {
13         cout<<"Find a path : ";
14         vector<int>::iterator iter = path.begin();
15         for (;iter != path.end() ; iter++)
16         {
17             cout<<*iter<<" ";
18         }
19         cout<<endl;
20     }
21     if (pRoot->m_pLeft)
22     {
23         FindPath(pRoot->m_pLeft ,expectedSum ,path ,currentSum);
24     }
25     if (pRoot->m_pRight)
26     {
27         FindPath(pRoot->m_pRight ,expectedSum ,path ,currentSum);
28     }
29     //currentSum = currentSum - path.back();
30     path.pop_back();
31 }
32 void FindPath(BinaryTreeNode* pRoot , int expectedSum)//用户接口
33 {
34     if (pRoot == NULL)
35     {
36         return;
37     }
38     int currentSum = 0 ;
39     vector<int> vec ;
40     FindPath(pRoot ,expectedSum ,vec , currentSum );
41 
42 }