題目：在二元樹中找出和為某一值的所有路徑
輸入一個整數和一棵二元樹。從樹的根結點開始往下訪問一直到葉結點所經過的所有結點形成一條路徑。打印出和與輸入整數相等的所有路徑。例如輸入整數22 和如下二元樹 10 / \ 5 12 / \ 4 7則打印出兩條路徑：10, 12 和10, 5, 7。思路
1、當訪問到某一節點時，把該結點的值添加到當前和變量，且把該結點壓入棧中。
2、若結點為葉子結點，且當前CurrentSum與期望的expectedSum相等，則打印棧中的結點值，即為所需的路徑。
3、若結點不是葉子結點，繼續訪問它的左孩子結點，訪問它的右孩子結點。
4、刪除該結點。包括從當前和變量中減去結點值，從棧中彈出結點值。此時，已回到父結點。
程序中的棧，利用STL中的vector，這樣簡化了編碼工作。
具體的findPath函數代碼如下：
[cpp]
void findPath(BtreeNode *root, int excepetedSum, vector<int> path, int currentSum) {
currentSum += root->v;
path.push_back(root->v);
if (root->left == NULL && root->right == NULL && currentSum == excepetedSum) {
vector<int>::iterator iter;
for (iter = path.begin(); iter != path.end(); iter++)
cout << *iter << " ";
}else {
if (root->left != NULL)
findPath(root->left, excepetedSum, path, currentSum);
if (root->right != NULL)
findPath(root->right, excepetedSum, path, currentSum);
}
currentSum -= root->v;
path.pop_back();
}
void findPath(BtreeNode *root, int excepetedSum, vector<int> path, int currentSum) {
currentSum += root->v;
path.push_back(root->v);
if (root->left == NULL && root->right == NULL && currentSum == excepetedSum) {
vector<int>::iterator iter;
for (iter = path.begin(); iter != path.end(); iter++)
cout << *iter << " ";
}else {
if (root->left != NULL)
findPath(root->left, excepetedSum, path, currentSum);
if (root->right != NULL)
findPath(root->right, excepetedSum, path, currentSum);
}
currentSum -= root->v;
path.pop_back();
}
上全部已測試通過的代碼：
[cpp] // printTreePathSum.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <vector>
#include <iostream>
using namespace std;
struct BtreeNode {
int v;
struct BtreeNode *left;
struct BtreeNode *right;
};
BtreeNode* insertNode(BtreeNode* root, int value) {
BtreeNode* ptr=root;
BtreeNode* tmpNode;
BtreeNode* newNode = (BtreeNode*)malloc(sizeof(struct BtreeNode));
newNode->v = value;
newNode->left = NULL;
newNode->right = NULL;
if (ptr == NULL)
return newNode;
while (ptr != NULL) {
tmpNode = ptr;
if (ptr->v < value)
ptr = ptr->right;
else
ptr = ptr->left;
}
if (tmpNode->v < value)
tmpNode->right = newNode;
else
tmpNode->left = newNode;
return root;
}
BtreeNode* buildTree() {
BtreeNode* root = NULL;
int a;
while (cin>>a) {
root = insertNode(root, a);
}
return root;
}
void findPath(BtreeNode *root, int excepetedSum, vector<int> path, int currentSum) {
currentSum += root->v;
path.push_back(root->v);
if (root->left == NULL && root->right == NULL && currentSum == excepetedSum) {
vector<int>::iterator iter;
for (iter = path.begin(); iter != path.end(); iter++)
cout << *iter << " ";
}else {
if (root->left != NULL)
findPath(root->left, excepetedSum, path, currentSum);
if (root->right != NULL)
findPath(root->right, excepetedSum, path, currentSum);
}
currentSum -= root->v;
path.pop_back();
}
int _tmain(int argc, _TCHAR* argv[])
{
BtreeNode* root;
root = buildTree();
vector<int> path;
findPath(root, 22, path, 0);
system("pause");
return 0;
}
// printTreePathSum.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <vector>
#include <iostream>
using namespace std;
struct BtreeNode {
int v;
struct BtreeNode *left;
struct BtreeNode *right;
};
BtreeNode* insertNode(BtreeNode* root, int value) {
BtreeNode* ptr=root;
BtreeNode* tmpNode;
BtreeNode* newNode = (BtreeNode*)malloc(sizeof(struct BtreeNode));
newNode->v = value;
newNode->left = NULL;
newNode->right = NULL;
if (ptr == NULL)
return newNode;
while (ptr != NULL) {
tmpNode = ptr;
if (ptr->v < value)
ptr = ptr->right;
else
ptr = ptr->left;
}
if (tmpNode->v < value)
tmpNode->right = newNode;
else
tmpNode->left = newNode;
return root;
}
BtreeNode* buildTree() {
BtreeNode* root = NULL;
int a;
while (cin>>a) {
root = insertNode(root, a);
}
return root;
}
void findPath(BtreeNode *root, int excepetedSum, vector<int> path, int currentSum) {
currentSum += root->v;
path.push_back(root->v);
if (root->left == NULL && root->right == NULL && currentSum == excepetedSum) {
vector<int>::iterator iter;
for (iter = path.begin(); iter != path.end(); iter++)
cout << *iter << " ";
}else {
if (root->left != NULL)
findPath(root->left, excepetedSum, path, currentSum);
if (root->right != NULL)
findPath(root->right, excepetedSum, path, currentSum);
}
currentSum -= root->v;
path.pop_back();
}
int _tmain(int argc, _TCHAR* argv[])
{
BtreeNode* root;
root = buildTree();
vector<int> path;
findPath(root, 22, path, 0);
system("pause");
return 0;
}
