学步园

题目：输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如 输入整数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
};

做这个联系的收获：vector的用法，递归思想的深入理解，熟练建树

注意：'\t'导致错误；建树时节点插入的顺序影响树的形状。

完整代码如下：

#include<stdio.h>
#include<iostream>
#include <vector>
#include<cstdlib>
using namespace std;


struct BinaryTreeNode // a node in the binary tree
{
	int m_nValue;
	BinaryTreeNode *m_pLeft;
	BinaryTreeNode *m_pRight;
};
 
void CreateTree(BinaryTreeNode *&p,int e)
{
	if(NULL==p)
	{
		BinaryTreeNode *node=new BinaryTreeNode();
		node->m_nValue=e;
		node->m_pLeft=NULL;
		node->m_pRight=NULL;
		p=node;
	}
	else
	{
		if(p->m_nValue>e)
			CreateTree(p->m_pLeft,e);
		else if(p->m_nValue<e)
			CreateTree(p->m_pRight,e);
		else cout<<"重复"<<endl;
	}
}
void FindPath(BinaryTreeNode *pTreeNode,int expectedSum,std::vector<int>& path,int& currentSum)
{
	if(!pTreeNode)
            return;

    currentSum += pTreeNode->m_nValue;
	path.push_back(pTreeNode->m_nValue);

    bool isLeaf = (NULL==pTreeNode->m_pLeft && NULL==pTreeNode->m_pRight);
    if(currentSum == expectedSum && isLeaf)
    {   
		std::vector<int>::iterator iter = path.begin();
         for(; iter != path.end(); ++ iter)
                 cout << *iter << '\t';//bug
         cout<<endl;
    }//迭代输出 

    if(pTreeNode->m_pLeft)
            FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum);
    if(pTreeNode->m_pRight)
            FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum);

    currentSum -= pTreeNode->m_nValue;
    path.pop_back();//删除容器的末元素，并不返回该元素。
}

void PrintTree(BinaryTreeNode *p)
{
	if(NULL==p)
		return;
	if(NULL!=p->m_pLeft)
		PrintTree(p->m_pLeft);
	cout<<p->m_nValue<<endl;//中序遍历
	if(NULL!=p->m_pRight)
		PrintTree(p->m_pRight);
}
void main()
{
	BinaryTreeNode *pRoot=NULL;//注意初始化
	CreateTree(pRoot,10);
	CreateTree(pRoot,5);
	CreateTree(pRoot,4);
	CreateTree(pRoot,7);
	CreateTree(pRoot,12);
	PrintTree(pRoot);

	int num=19;
	int sum=0;
	std::vector<int> v;
	FindPath(pRoot,num,v,sum);
}