找出二叉树中和为n的路径
题目描述：
输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。
二叉树中的路径
从二叉树的根节点出发，至二叉树的叶子节点的一条直线，称为二叉树的一条路径
例如：输入整数22和如下二元树
10
/
5 12
/
4 7
则打印出两条路径:10, 12和10, 5, 7。
思路：
从二叉树的根节点出发，并将该节点入栈，更新currentSum的值，再遍历该节点的左子树，直到叶子节点后，判断currentSum的值，判断与输入值比较后，返回该叶子节点的父亲节点，并弹出栈顶元素，继续遍历父亲节点的右子树，直到叶节点。重复以上步骤，知道所有节点遍历完后。
代码实现
include <iostream>
#include <vector>
#include "tree.h"
#include <cstring>
using namespace std;
void Find(vector<int>&, BTNode*, int, int);
// 寻找路径
void FindPath(BTNode *root, int pathSum)
{
vector<int> path;
int currentSum=0;
memset(&path, 0, sizeof(path));
Find(path, root, pathSum, currentSum);
}
void Find(vector<int> &path, BTNode *root, int pathSum, int currentSum)
{
currentSum += root->data; //记录当前路径的和
path.push_back(root->data); //将当前节点值压栈
//判断当前节点是不是叶子节点
bool isLeaf = root->left==NULL && root->right==NULL;
//该节点是叶子节点，且路径的和符合要求，则打印路径
if(currentSum == pathSum && isLeaf)
{
cout << "A path is found: "<< endl;
vector<int>::iterator it = path.begin();
for(; it!=path.end(); it++)
cout << *it << " ";
cout << endl;
}
//遍历该节点的左子树
if(root->left!=NULL)
Find(path, root->left, pathSum, currentSum);
//遍历该节点的右子树
if(root->right!=NULL)
Find(path, root->right, pathSum, currentSum);
//在返回父节点之前，将父节点弹栈
path.pop_back();
}
//测试
int main(void)
{
int data[] = {5, 10, 5, 12, 4, 7};
BTNode *root = NULL;
int pathSum = 22;
insert_node(&root, data, 1);
FindPath(root, pathSum);
return 0;
}
其中二叉树的数据结构定义为
struct BTNode
{
int data;
BTNode *left;
BTNode *right;
};
//先序建立二叉树
void insert_node(BTNode **root, int *data, int i)
{
if(i<=data[0])
{
*root = new BTNode();
(*root)->data = data[i];
(*root)->left=NULL;
(*root)->right=NULL;
insert_node(&((*root)->left), data, 2*i);
insert_node(&((*root)->right), data, 2*i+1);
}
}
void remove_node(BTNode *root)
{
if(root!=NULL)
{
BTNode *pDel = NULL;
remove_node(root->left);
remove_node(root->right);
delete root;
}
}
(以上部分摘抄自<<剑指Offer>>)
