题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。
例如输入整数22和如下二元树
10
/ \
5 12
/ \
4 7
则打印出两条路径：10, 12和10, 5, 7。
#include <iostream>
using namespace std;
#include <vector>
using std::vector;
#include <stdio.h>
template<typename T>
class TreeNode
{
public:
TreeNode(T val);
TreeNode *getLeftChild();
TreeNode *getRightChild();
void setLeftChild( TreeNode *lChild );
void setRightChild( TreeNode *rChild );
T getValue();
private:
T mValue;
TreeNode *mLeftChild;
TreeNode *mRightChild;
};
template<typename T>
TreeNode<T>::TreeNode(T val):mValue(val),mLeftChild(0),mRightChild(0)
{
}
template<typename T>
T
TreeNode<T>::getValue()
{
return mValue;
}
template<typename T>
TreeNode<T>*
TreeNode<T>::getLeftChild()
{
return mLeftChild;
}
template<typename T>
TreeNode<T>*
TreeNode<T>::getRightChild()
{
return mRightChild;
}
template<typename T>
void
TreeNode<T>::setLeftChild(TreeNode *lChild)
{
mLeftChild = lChild;
}
template<typename T>
void
TreeNode<T>::setRightChild( TreeNode *rChild )
{
mRightChild = rChild;
}
template<typename T>
TreeNode<T>*
buildTree()
{
TreeNode<int> *r10 = new TreeNode<int>(10);
TreeNode<int> *r5 = new TreeNode<int>(5);
TreeNode<int> *r12 = new TreeNode<int>(12);
TreeNode<int> *r4 = new TreeNode<int>(4);
TreeNode<int> *r7 = new TreeNode<int>(7);
r10->setLeftChild(r5);
r10->setRightChild(r12);
r5->setLeftChild(r4);
r5->setRightChild(r7);
return r10;
}
template<typename T>
void
Travese(TreeNode<T> *node,T expectValue,vector<T> &path, T & currentValue)
{
if ( node == 0 )
{
return ;
}
fprintf(stderr,"Travese value %d %d\n",node->getValue(),currentValue);
T value = node->getValue();
currentValue += value;
path.push_back(value);
bool isLeaf = (!node->getLeftChild()) && ((!node->getRightChild()));
if ( expectValue == currentValue && isLeaf )
{
size_t vectSize = path.size();
for ( int i = 0 ; i < vectSize ; i ++ )
{
cout << path[i]<<endl;
}
}
if ( node->getLeftChild() )
{
Travese( node->getLeftChild(),expectValue,path,currentValue );
}
if ( node->getRightChild() )
{
Travese( node->getRightChild(),expectValue,path,currentValue );
}
currentValue -= value;
path.pop_back();
}
int main(int argc, char *argv[])
{
TreeNode<int> *node = buildTree<int>();
vector<int> result;
int currentValue = 0;
Travese(node,22,result,currentValue);
return 0;
}