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

例如：

10
/     \
5       12
/ \
4   7

输入整数22，输出如下路径：

10  12
10  5  7

解：就是最简单的先序遍历，只不过要记录路径，可以使用数组，我这里用的stl::vector。

注意left和right遍历后，要回退当前结点在path中状态。

算法：

void bitree_path(struct BiTree* tree, int value, ::std::vector<int>& path)
{
	// Add current to path
	path.push_back(tree->data);
	// Arrive at leaf node
	if(tree->left==NULL && tree->right==NULL)
	{
		int sum = 0;
		for(int i=0;i<path.size();i++)	
		{
			sum+=path[i];
		}
		if(sum==value)
		{
			for(int i=0;i<path.size();i++)
			{
				::std::cout << path[i] << " ";
			}
			::std::cout << ::std::endl;
		}
	} else {
		// Left
		bitree_path(tree->left, value, path);
		// right
		bitree_path(tree->right, value, path);
	}
	// Remove current from path
	path.pop_back();
}

其他树定义，创建等的实现如下：

#include <iostream>
#include <vector>

#define EMPTY -1

struct BiTree
{
	struct BiTree* left;
	struct BiTree* right;
	int data;
};

int pos = 0;
void bitree_init(struct BiTree* & tree, int *data, int n)
{
	if(pos>=n)
	{
		return ;
	}
	if(data[pos]!=EMPTY)
	{
		tree = new BiTree();	
		tree->data = data[pos];
		pos++;
		bitree_init(tree->left, data, n);
		pos++;
		bitree_init(tree->right, data, n);
	}else
	{
		tree = NULL;
	}
}

void bitree_pre_order(struct BiTree* tree)
{
	if(tree!=NULL)
	{
		::std::cout << tree->data << " ";
		bitree_pre_order(tree->left);
		bitree_pre_order(tree->right);
	}
}

<br class="brush: cpp; gutter: true" />int main()
{
	struct BiTree* tree = NULL;
	int data[11] = {10, 5, 4, EMPTY, EMPTY, 7, EMPTY, EMPTY, 12, EMPTY, EMPTY};
	pos = 0;
	bitree_init(tree, data, sizeof(data)/sizeof(int));
	bitree_pre_order(tree);
	::std::cout &lt;&lt; ::std::endl;
	::std::vector&lt;int&gt; path;
	bitree_path(tree, 22, path);
	return 0;
}