题目
原文：
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.
译文：
给定一棵二叉树，每个结点包含一个值。打印出所有满足以下条件的路径： 路径上结点的值加起来等于给定的一个值。注意：这些路径不必从根结点开始。
解答
方案1：如果结点中包含指向父亲结点的指针，那么，只需要去遍历这棵二叉树， 然后从每个结点开始，不断地去累加上它父亲结点的值直到父亲结点为空(这个具有唯一性， 因为每个结点都只有一个父亲结点。也正因为这个唯一性， 可以不另外开额外的空间来保存路径)，如果等于给定的值sum，则打印输出。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
void find_sum(Node* head, int sum){
if(head == NULL) return;
Node *no = head;
int tmp = 0;
for(int i=1; no!=NULL; ++i){
tmp += no->key;
if(tmp == sum)
print(head, i);
no = no->parent;
}
find_sum(head->lchild, sum);
find_sum(head->rchild, sum);
}
打印输出时，只需要提供当前结点的指针，及累加的层数即可。然后从当前结点开始， 不断保存其父亲结点的值(包含当前结点)直到达到累加层数，然后逆序输出即可。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
void print(Node* head, int level){
vector<int> v;
for(int i=0; i<level; ++i){
v.push_back(head->key);
head = head->parent;
}
while(!v.empty()){
cout<<v.back()<<" ";
v.pop_back();
}
cout<<endl;
}
方案2：如果结点中不包含指向父亲结点的指针，则在二叉树从上向下查找路径的过程中， 需要为每一次的路径保存中间结果，累加求和仍然是从下至上的，对应到保存路径的数组， 即是从数组的后面开始累加的，这样能保证遍历到每一条路径。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void print2(vector<int> v, int level){
for(int i=level; i<v.size(); ++i)
cout<<v.at(i)<<" ";
cout<<endl;
}
void find_sum2(Node* head, int sum, vector<int> v, int level){
if(head == NULL) return;
v.push_back(head->key);
int tmp = 0;
for(int i=level; i>-1; --i){
tmp += v.at(i);
if(tmp == sum)
print2(v, i);
}
vector<int> v1(v), v2(v);
find_sum2(head->lchild, sum, v1, level+1);
find_sum2(head->rchild, sum, v2, level+1);
}
方案1和方案2的本质思想其实是一样的，不同的只是有无指向父亲结点的指针这个信息。 如果没有这个信息，则需要增加许多额外的空间来存储中间信息。
注意：方案1和方案2代码中的level并非指同一概念，方案1中level表示层数，最小值为1； 方案2中level表示第几层，最小值为0。
完整代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 100;
struct Node{
int key;
Node *lchild, *rchild, *parent;
};
Node node[maxn];
int cnt;
void init(){
memset(node, '\0', sizeof(node));
cnt = 0;
}
void create_minimal_tree(Node* &head, Node *parent, int a[], int start, int end){
if(start <= end){
int mid = (start + end)>>1;
node[cnt].key = a[mid];
node[cnt].parent = parent;
head = &node[cnt++];
create_minimal_tree(head->lchild, head, a, start, mid-1);
create_minimal_tree(head->rchild, head, a, mid+1, end);
}
}
void print(Node* head, int level){
vector<int> v;
for(int i=0; i<level; ++i){
v.push_back(head->key);
head = head->parent;
}
while(!v.empty()){
cout<<v.back()<<" ";
v.pop_back();
}
cout<<endl;
}
void find_sum(Node* head, int sum){
if(head == NULL) return;
Node *no = head;
int tmp = 0;
for(int i=1; no!=NULL; ++i){
tmp += no->key;
if(tmp == sum)
print(head, i);
no = no->parent;
}
find_sum(head->lchild, sum);
find_sum(head->rchild, sum);
}
void print2(vector<int> v, int level){
for(int i=level; i<v.size(); ++i)
cout<<v.at(i)<<" ";
cout<<endl;
}
void find_sum2(Node* head, int sum, vector<int> v, int level){
if(head == NULL) return;
v.push_back(head->key);
int tmp = 0;
for(int i=level; i>-1; --i){
tmp += v.at(i);
if(tmp == sum)
print2(v, i);
}
vector<int> v1(v), v2(v);
find_sum2(head->lchild, sum, v1, level+1);
find_sum2(head->rchild, sum, v2, level+1);
}
int main(){
init();
int a[] = {
4, 3, 8, 5, 2, 1, 6
};
Node *head = NULL;
create_minimal_tree(head, NULL, a, 0, 6);
// find_sum(head, 8);
vector<int> v;
find_sum2(head, 8, v, 0);
return 0;
}
全书题解目录：
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上：
https://github.com/Hawstein/cracking-the-coding-interview
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2012/12/31/4.8/
