首页 / 操作系统 / Linux / 求二叉树中和为给定值的所有路径

问题定义：You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree-it does not have to start at the root.解题思路：一层一层的遍历，保存当前节点到根节点的完整路径，然后从当前节点向上扫描，如果找到了当前节点到某个节点的和等于给定值，则输出之。程序对每个节点都需要遍历一遍，还要扫描当前节点到根节点的路径，且需要保存每个节点到根节点的路径，所以时间复杂度为O（nlgn），空间复杂度为O（nlgn）。（ps：关于本程序中建树部分，可以参考： http://www.linuxidc.com/Linux/2012-05/61459.htm ）代码实例：

1. #include <algorithm>   
2. #include <iostream>   
3. #include <time.h>   
4. #include <assert.h>   
5. #include <stdio.h>   
6. #include <vector>   
7.   
8.   
9. using namespace std;  
10.   
11. struct node   
12. {  
13.     int data;  
14.     struct node * lchild;  
15.     struct node * rchild;  
16. };  
17.   
18.   
19. //将数组转换为深度最低的二叉树，采用了二分查找的思想   
20. struct node* ConvertArrayToTree（int data[], int first, int last）  
21. {  
22.     if （last < first）   
23.     {  
24.         return NULL;  
25.     }  
26.     else  
27.     {  
28.         int mid = （ last + first ） / 2;  
29.         struct node * newNode = NULL;  
30.         newNode = （struct node *）malloc（sizeof（struct node））;  
31.         newNode->data = data[mid];  
32.         newNode->lchild = ConvertArrayToTree（data, first, mid - 1）;  
33.         newNode->rchild = ConvertArrayToTree（data, mid + 1, last）;  
34.         return newNode;  
35.     }  
36. }  
37.   
38. //再最左边插入一个节点   
39. void InsertNodeAtLeft（struct node *root, struct node *newNode）  
40. {  
41.     assert（root ！= NULL && newNode ！= NULL）;  
42.     while（root->lchild ！= NULL）  
43.     {  
44.         root = root->lchild;  
45.     }  
46.     root->lchild = newNode;  
47. }  
48.   
49. //在最右边插入一个节点   
50. void InsertNodeAtRight（struct node *root, struct node *newNode）  
51. {  
52.     assert（root ！= NULL && newNode ！= NULL）;  
53.     while（root->rchild ！= NULL）  
54.     {  
55.         root = root->rchild;  
56.     }  
57.     root->rchild = newNode;  
58. }  
59. //中序遍历   
60. void Traverse（struct node *root）  
61. {  
62.     if （root == NULL）   
63.     {  
64.         return;  
65.     }  
66.     Traverse（root->lchild）;  
67.     Traverse（root->rchild）;  
68.     printf（"%d ", root->data）;  
69. }  
70.   
71. //打印和为sum的路径   
72. void print（vector<int>& buffer, int first, int last）  
73. {  
74.     int i;  
75.     for （i = first; i <= last; i++）   
76.     {  
77.         cout << buffer[i] << " ";  
78.     }  
79.     cout << endl;  
80. }  
81. void findSum（struct node *head, int sum, vector<int> &buffer, int level）  
82. {  
83.     if （head == NULL） return;  
84.   
85.     int i;  
86.     int tmp = sum;  
87.     buffer.push_back（head->data）;  
88.     for （i = level; i >= 0; i--）  
89.     {  
90.         tmp -= buffer[i];  
91.         if （tmp == 0） print（buffer, i, level）;  
92.     }  
93.   
94.     vector<int> lbuffer（buffer）;  
95.     vector<int> rbuffer（buffer）;  
96.   
97.     findSum（head->lchild, sum, lbuffer, level + 1）;  
98.     findSum（head->rchild, sum, rbuffer, level + 1）;  
99. }  
100.   
101. int main（int argc, char* argv[]）  
102. {  
103.     const int SIZE = 10;//测试的数据量   
104.     int data[SIZE];//保存数据   
105.     int i, j;  
106.     struct node *head = NULL;  
107.   
108.     for （i = 0; i < SIZE; i++）   
109.     {  
110.         data[i] = i + 1;  
111.     }  
112.   
113.     head = ConvertArrayToTree（data, 0, SIZE - 1）;  
114.   
115.     struct node *one = （struct node *）malloc（sizeof（struct node））;  
116.     struct node *two = （struct node *）malloc（sizeof（struct node））;  
117.     one->data = 11;  
118.     one->lchild = NULL;  
119.     one->rchild = NULL;  
120.       
121.     two->data = 4;  
122.     two->lchild = NULL;  
123.     two->rchild = NULL;  
124.   
125.     InsertNodeAtLeft（head, one）;  
126.     InsertNodeAtRight（head, two）;  
127.     //遍历数据   
128. //  Traverse（head）;   
129. //  printf（" "）;   
130.     vector<int> v;  
131.     findSum（head, 14, v, 0）;  
132.     return 0;  
133. }  

该示例中所使用的二叉树如下所示：
运行结果如下：