面试题25.二叉树中和为某一值的路径

题目:输入一颗二叉树和一个整数,打印出二叉树中借点值得和为输入整数的所有路径。

从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

二叉树结点定义:

1 struct BinaryTreeNode
2 {
3     int m_nValue;
4     BinaryTreeNode* m_pLeft;
5     BinaryTreeNode* m_pRight;
6 }

我们以二叉树:

1 　　　　　8
2        /  
4       6   10
6    　/   / 
8     5  7 9  11

为例，当我们想要找到值为21的路径的时候。

步骤如下:

1.收到从根元素开始寻找路径，则在二叉树的三种遍历顺序中只有前序遍历

满足条件。

2.接下来向左子树遍历到元素6，此时8+6=14仍然不等于21

3.继续向左子树遍历到元素5，此时8+6+5=19

4.发现此时元素5已经是叶子节点了，则退回到元素6，向右节点遍历到

元素7，此时8+6+7=21满足条件输出8，6,7

5.继续用同样的方式递归该二叉树的右子树即可。

这里存储路径的数据结构可以是stack可以是vector，用vector的原因是

方便输出

代码实现如下:

 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 using namespace std;
 5 
 6 struct BinaryTreeNode
 7 {
 8      int m_nValue;
 9      BinaryTreeNode* m_pLeft;
10      BinaryTreeNode* m_pRight;
11 };
12 
13 void CreateTree(BinaryTreeNode** Root)
14 {
15     int data;
16     cin>>data;
17     if(data==0)
18     {
19         *Root=NULL;
20         return ;
21     }
22     else
23     {
24         *Root=(BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
25         (*Root)->m_nValue=data;
26         CreateTree(&((*Root)->m_pLeft));    
27         CreateTree(&((*Root)->m_pRight));
28     }
29 }
30 
31 
32 void PreOrder(BinaryTreeNode* Root)
33 {
34     if(Root==NULL)
35         return;
36 
37     cout<<Root->m_nValue<<endl;
38     PreOrder(Root->m_pLeft);
39     PreOrder(Root->m_pRight);    
40 }
41 
42 
43 void FindPath(BinaryTreeNode* root,vector<int>& VecPath,int Sum,int NowSum)
44 {
45     NowSum=NowSum+root->m_nValue;
46     VecPath.push_back(root->m_nValue);
47 
48     bool yezi=root->m_pLeft==NULL&&root->m_pRight==NULL;
49     if(NowSum==Sum&&yezi)
50     {
51         cout<<"Find Path of Number "<<Sum<<":    ";
52         for(vector<int>::iterator iter=VecPath.begin();iter!=VecPath.end();iter++)
53         {
54             cout<<*iter<<" ";
55         }
56         cout<<endl;
57     }
58 
59     if(root->m_pLeft!=NULL)
60     {
61         FindPath(root->m_pLeft,VecPath,Sum,NowSum);
62     }
63 
64     if(root->m_pRight!=NULL)
65     {
66         FindPath(root->m_pRight,VecPath,Sum,NowSum);
67     }
68     VecPath.pop_back();
69 }
70 
71 
72 void FindPathOfNumber(BinaryTreeNode* root,int Sum)
73 {
74     if(root==NULL)
75         return;
76 
77     vector<int> VecPath;
78     int NowSum=0;
79     FindPath(root,VecPath,Sum,NowSum);
80 }
81 
82 
83 int main()
84 {
85     BinaryTreeNode* root;
86     cout<<"Please input the tree node data(0-exit):
";
87     CreateTree(&root);
88     cout<<"The PreOrder of Binary Tree:
";
89     PreOrder(root);
90     cout<<endl;
91     int num;
92     cout<<"Please input the path sum you want to find: ";
93     cin>>num;
94     FindPathOfNumber(root,num);
95     system("pause");
96     return 0;
97 }

运行截图: