求二叉樹中和為給定值的所有路徑

問題定義：

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>
9. using namespace std;
11. struct node
12. {
13. int data;
14. struct node * lchild;
15. struct node * rchild;
16. };
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. }
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. }
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\t", root->data);
69. }
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] << "\t";
78. }
79. cout << endl;
80. }
81. void findSum(struct node *head, int sum, vector<int> &buffer, int level)
82. {
83. if (head == NULL) return;
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. }
94. vector<int> lbuffer(buffer);
95. vector<int> rbuffer(buffer);
97. findSum(head->lchild, sum, lbuffer, level + 1);
98. findSum(head->rchild, sum, rbuffer, level + 1);
99. }
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;
108. for (i = 0; i < SIZE; i++)
109. {
110. data[i] = i + 1;
111. }
113. head = ConvertArrayToTree(data, 0, SIZE - 1);
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;
121. two->data = 4;
122. two->lchild = NULL;
123. two->rchild = NULL;
125. InsertNodeAtLeft(head, one);
126. InsertNodeAtRight(head, two);
127. //遍歷數據
128. // Traverse(head);
129. // printf("\n");
130. vector<int> v;
131. findSum(head, 14, v, 0);
132. return 0;
133. }

運行結果如下：