剑指offer 面试题25—二叉树中和替某一值的路径

剑指offer 面试题25—二叉树中和为某一值的路径

题目：

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

基本思想：

规律：

遍历到某一节点时，将节点添加到路径中，并累加该节点的值。如果该节点为叶节点并且路径中节点值的和等于输入整数，打印路径节点序列。

不是，则继续访问它的子节点。当前节点访问结束后，递归函数将自动回到它的父节点。因此我们在函数退出之前要在路径上删除当前节点并减去当前节点的值。

#include <iostream>
#include <vector>
using namespace std;

//二叉树结点定义
typedef struct BiTreeNode{
	int data;
	//左右孩子指针
	struct BiTreeNode *lchild;
	struct BiTreeNode *rchild;
}BiTreeNode,*BiTree;

//按先序序列创建二叉树
int CreateBiTree(BiTree &T)
{
	int data;
	//按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树
	cin>>data;
	if(data == -1)
	{
		T = NULL;
	}
	else
	{
		T = (BiTree)malloc(sizeof(BiTreeNode));
		T->data = data;//生成根结点		
		CreateBiTree(T->lchild);//构造左子树		
		CreateBiTree(T->rchild);//构造右子树
	}
	return 0;
}

void findpath(BiTree T,int n,vector<int> path,int cursum)
{
	cursum+=T->data;
	path.push_back(T->data);

	bool isLeaf=T->lchild==NULL && T->rchild==NULL;

	//如果是叶节点，并且路径上节点的和等于输入的值，打印这条路径
	if(cursum==n && isLeaf)
	{
		vector<int>::iterator i = path.begin();
		for(;i!=path.end();++i)
			cout<<*i<<" ";
		cout<<endl;
	}

	//如果不是叶节点，则遍历它的子节点
	if(T->lchild!=NULL)
		findpath(T->lchild,n,path,cursum);
	if(T->rchild!=NULL)
		findpath(T->rchild,n,path,cursum);

	//在返回父节点之前，在路径上删除当前节点
	path.pop_back();
}

void foo(BiTree T,int n)
{
	if(T == NULL)
		return;

	vector<int> path;
	int cursum=0;
	findpath(T,n,path,cursum);
}


void main()
{
	BiTree T;
	CreateBiTree(T);

	int n;
	cin>>n;

	foo(T,n);
}