二叉树中和为某一值的路径

我们举例来做分析，如下图所示，我们准备了一颗二叉树和一个整数22，通过观察后，我们很容易就能看出它有两条路径的节点值加起来和为22。,,上述两个路径都是从根节点出发到叶子节点的，也就是说路径总是以根节点为起始点，因此我们首先需要遍历根节点。在树的三种遍历方式中，只有前序遍历是首先访问根节点的。,按照前序遍历的顺序去访问这颗二叉树，在访问节点10之后，就会访问节点5。图中二叉树并没有指向父节点的指针，当访问节点5的时候，我们是不知道前面经过了哪些节点的，此时我们就需要准备一个栈，用来存储访问过的节点。,当到达节点5的时候，路径中包含两个节点：10、5。接下来遍历到节点4，我们把这个节点入栈，这时候已经到达叶节点，但栈中的所有节点之和是19。这个和不等于输入的值22，因此它不符合要求的路径。,最后，我们要遍历的节点是12。在遍历这个节点之前，需要先经过节点5回到节点10。同样的，每次当从子节点回到父节点的时候，我们都需要在路径上删除子节点。最后在节点10到达节点12的时候，路径上的两个节点的值之和也是22，因此这也是一条符合要求的路径。,递归上述过程，直至二叉树的所有节点访问完毕。,,形成了清晰的思路之后，接下来我们就可以轻松的写出代码了，如下所示：,接下来我们用文章开头的例子来测试下上述代码能否正确执行。,如下所示，成功得计算出了两条路径。,,我们将节点12改成20，再来测试下，结果如下所示，只有一条路径符合预期。,,本文用到的代码完整版请移步：