《剑指Offer》学习笔记--面试题25：二叉树中和为某一直的路径

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

二叉树结点定义如下：

struct BinaryTreeNode
{
	int           m_nValue;
	BinaryTreeNode* m_pLeft;
	BinaryTreeNode* m_pRight;
};

一般的数据结构和算法的教材都没有介绍树的路径，因此对大多数应聘者而言，这是一个新概念，也就很难一下子想出完整的解题思路。这个时候我们可以试着从一两个具体的例子入手，找到规律。

由于路径是从根结点出发到叶结点，也就是说路径总是以根结点为起始点，因此我们首先需要遍历根结点。在树的前序，中序和后序三种遍历方式中，只有前序遍历是先访问根结点。我们可以找到一些规律：当用前序遍历的方式访问到某一结点时，我们把该结点添加到路径上，并累加该结点的值。如果该结点为叶结点并且路径中结点值的和刚好等于输入的整数，则当前的路径符合要求，我们把它打印出来。如果当前的结点不是叶节点，则继续访问它的子结点。当前结点访问结束后，递归函数将自动回到它的父节点。因此我们在函数退出之前要再路径上删除当前结点并减去当前结点的值，以确保返回的父结点时路径刚好是从根结点到父结点的路径。我们不难看出保存路径的数据结构实际上是一个栈，因为路径要与递归调用状态一致，而递归调用本质就是一个压栈和出栈的过程。

下面是参考代码：

void FindPath(BinaryTreeNode* pRoot, int expectedSum)
{
	if(pRoot == NULL)
		return;

	std::vector<int> path;
	int currentSum = 0;
	FindPath(pRoot, expectedSum, path, currentSum);
}

void FindPath
	(
	    BinaryTreeNode* pRoot,
		int            expectedSum,
		std::vector<int>& path,
		int            currentSum
	)
{
	currentSum += pRoot->m_nValue;
	path.push_back(pRoot->m_nValue);

	//如果是叶结点，并且路径上结点的和等于输入的值
	//打印出这条路径
	bool isLeaf = pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL;
	if(currentSum == expectedSum && isLeaf){
		printf("A path is found: ");
		std::vector<int>::iterator iter = path.begin();
		for(; iter != path.end(); ++ iter)
			printf("%d", *iter);
		printf("\n");		
	}

	//如果不是叶结点，则遍历它的子结点
	if(pRoot->m_pLeft != NULL)
		FindPath(pRoot->m_pLeft, expectedSum, path, currentSum);
	if(pRoot->m_pRight != NULL)
		FindPath(pRoot->m_pRight, expectedSum, path, currentSum);

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

在前面的代码中，我们用标准库模板中的vector实现了一个栈来保存路径，每一次都用push_back在路径的末尾添加结点，用pop_back在路径的末尾删除结点，这样就保证了栈的先入后出的特性。这里没有直接用STL中stack的原因实在stack中只能得到栈顶元素，而我们打印路径的时候需要得到路径上的所有结点，因此在代码实现的时候std::stack不是最好的选择。