Question

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

例如输入图4.7中二叉树和整数22，则打印出两条路径，第一条路径包含结点10、12，第二条路径包含结点10、5和7。

图4.7　二叉树中有两条和为22的路径：一条路径经过结点10、5、7，另一条路径经过结点10、12

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

以图4.7的二叉树作为例子来分析。由于路径是从根结点出发到叶结点，也就是说路径总是以根结点为起始点，因此我们首先需要遍历根结点。在树的前序、中序、后序三种遍历方式中，只有前序遍历是首先访问根结点的。

按照前序遍历的顺序遍历图4.7中的二叉树，在访问结点10之后，就会访问结点5。从二叉树结点的定义可以看出，在本题的二叉树结点中没有指向父结点的指针，访问到结点5的时候，我们是不知道前面经过了哪些结点的，除非我们把经过的路径上的结点保存下来。每访问到一个结点的时候，我们都把当前的结点添加到路径中去。到达结点5时，路径中包含两个结点，它们的值分别是10和5。接下来遍历到结点4，我们把这个结点也添加到路径中。这个时候已经到达了叶结点，但路径上三个结点的值之和是19。这个和不等于输入的值22，因此不是符合要求的路径。

我们接着要遍历其他的结点。在遍历下一个结点之前，先要从结点4回到结点5，再去遍历结点5的右子结点7。值得注意的是，回到结点5的时候，由于结点4已经不在前往结点7的路径上了，我们需要把结点4从路径中删除。接下来访问到结点7的时候，再把该结点添加到路径中。此时路径中三个结点10、5、7之和刚好是22，是一条符合要求的路径。

我们最后要遍历的结点是12。在遍历这个结点之前，需要先经过结点5回到结点10。同样，每一次当从子结点回到父结点的时候，我们都需要在路径上删除子结点。最后从结点10到达结点12的时候，路径上的两个结点的值之和也是22，因此这也是一条符合条件的路径。

我们可以用表4.5总结上述的分析过程。

表4.5　遍历图4.7中的二叉树的过程

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

形成了清晰的思路之后，就可以动手写代码了。下面是一段参考代码：

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

源代码：

本题完整的源代码详见25_PathInTree项目。

测试用例：

- 功能测试（二叉树中有一条、多条符合条件的路径，二叉树中没有符合条件的路径）。

- 特殊输入测试（指向二叉树根结点的指针为NULL指针）。

本题考点：

- 考查分析复杂问题的思维能力。应聘者遇到这个问题的时候，如果一下子没有思路，不妨从一个具体的例子开始，一步步分析路径上包含哪些结点，这样就能找出其中的规律，从而想到解决方案。

- 考查对二叉树的前序遍历的理解。