每日一算法（在二元树中找出和为某一值的所有路径（树））

每天一算法（在二元树中找出和为某一值的所有路径（树））

题目：

输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。
例如 

输入整数22和如下二元树
     10  
    /    \
 5    12   
  /  \   
      4     7
则打印出两条路径：10, 12和10, 5, 7。

二元树节点的数据结构定义为：
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};

解题思路：

递归的思想。很多树的题目都是用递归解决的，例如把二元查找树转变成排序的双向链表（树）。递归的终止条件为当前为空结点或当前结点的值大于剩余和。如果当前结点的值等于剩余和，并且是叶结点，那么打印路径。否则，将剩余和减去当前结点的值，递归求解。至于路径的记录，可以利用栈的思想来实现。

VS2010中运行程序如下：例子程序是正确的，，如果有什么错误，希望各位高手指定，，呵呵。。

#include<iostream>
#include<vector>
#include<limits.h>
#include<assert.h>
using namespace std;
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};
//二叉树的构建。
BinaryTreeNode* AddNode(BinaryTreeNode *& Root,int Value)
{
	//BinaryTreeNode *node = new BinaryTreeNode;
	//node->m_nValue = Value;
	//node->m_pLeft = node->m_pRight = NULL;
	if(NULL == Root)
	{
		Root = new BinaryTreeNode;
		Root->m_nValue = Value;
		Root->m_pLeft = NULL;
		Root->m_pRight = NULL;
		return Root;
	}
	//else
		if(Root->m_nValue > Value)
			return AddNode(Root->m_pLeft,Value);
		else
			return AddNode(Root->m_pRight,Value);
	//return Root;
}
//找到所有路径

void FindAllPath(BinaryTreeNode * Root,vector<int> &vec,
	const int Sum,int& CurrentSum)
{
	if(NULL == Root)
		return ;
	if(INT_MIN == CurrentSum)
		CurrentSum = Root->m_nValue;
	else
		CurrentSum += Root->m_nValue;
	vec.push_back(Root->m_nValue);
	if(Sum == CurrentSum)
	{
		vector<int>::iterator i = vec.begin();
		for(i;i<vec.end();i++)
			cout<<*i<<' ';
		cout<<endl;
	}
	else 
		if(Sum < CurrentSum)
		{
			vec.pop_back();
			CurrentSum -= Root->m_nValue;
			return ;
		}
		else
			{
				if(NULL != Root->m_pLeft)
					FindAllPath(Root->m_pLeft,vec,Sum,CurrentSum);
				else
				{
					vec.pop_back();
					CurrentSum -= Root->m_nValue;
					return;
				}
				
				if(NULL != Root->m_pRight)
					FindAllPath(Root->m_pRight,vec,Sum,CurrentSum);
				else
				{
					vec.pop_back();
					CurrentSum -= Root->m_nValue;
					return;
				}
			}

	vec.pop_back();
	CurrentSum -= Root->m_nValue;
	return;


}

int main()
{
	BinaryTreeNode *Root;
	Root = NULL;
	AddNode(Root,10);
	AddNode(Root,5);
	AddNode(Root,12);
	AddNode(Root,4);
	AddNode(Root,7);
	int CurrentSum = INT_MIN;
	vector<int> vec;
	FindAllPath(Root,vec,22,CurrentSum);
	//cout<<Root->m_nValue;
	//cout<<Root->m_pRight->m_nValue;
	//cout<<Root->m_pLeft->m_nValue;

	return 0;
}