5.3 路径和系列问题
力扣（LeetCode）中的路径和系列问题是典型的可以用DFS来解决的题目。
5.3.1 路径总和
题目描述（第112题）
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明：叶子节点是指没有子节点的节点。
示例：给定如下二叉树，以及目标和sum=22。
返回True，因为存在目标和为22的根节点到叶子节点的路径5→4→11→2。
解法一 DFS递归
思路
题目要求找到一条根节点到叶子节点的路径，并且路径上所有节点的值之和等于给定的目标值。也就是说，需要搜索这个二叉树的不同路径（根节点到叶子节点）。如果找到一条符合条件的路径，则返回True；如果所有的路径都不符合要求，则返回False。因为题目要求只需要找到一条符合要求的路径，所以可以使用DFS来处理。
一种直观的思路是自顶向下，使用前序遍历+参数扩展，在向下递归的同时更新参数，当到达叶子节点或空节点时判断是否满足条件。在这里，我们可以将目标和sum通过参数扩展的形式向下传递，在叶子节点上判断当前节点的val是否等于传递下来的参数sum。这是一种非常常见的DFS解题思路，除了前序遍历，还有一种常见的二叉树的深度遍历法是后序遍历，即在递归函数返回时对问题进行求解，使用子树的返回值来计算当前节点的返回值。
通常来讲，DFS有递归和迭代两种实现方式。因为树结构天然具有递归的特性（子树性质和整个树性质一致），使用递归可以很容易地将整个树问题转换成子树问题。当我们层层递归到最小的子树时，这个最小子树的解（也被称为递归出口）往往很容易就能够得到，再一步步回溯就能得到原问题的解。
小提示：树的题目，优先考虑使用DFS递归解决。
当我们处理递归问题时，如何定义递归出口是非常重要的一步（递归出口指的是递归函数可以直接处理的最简单子问题）。对于本题，递归出口是当当前子树只有一个节点时（该节点是整个树的叶子节点），需要在递归出口判断当前路径是否符合要求。
一般这种有关树的DFS题目，递归出口都是叶子节点或空节点。
代码
复杂度分析
● 时间复杂度：在最坏情况下，我们会访问每个节点各一次，因此时间复杂度为O(n)，其中n是节点个数。
● 空间复杂度：所需额外的空间和树的高度呈线性关系。在最坏情况下，整个树是非平衡的，每个节点都只有一个子节点，完全变为单链表的形态，此时树的高度是n，因此栈的空间开销是O(n)，但在最好情况下，树是完全平衡的，高度为logn，在这种情况下空间复杂度只有O(logn)。
解法二 DFS迭代
思路
对于上面递归的写法，我们可以使用辅助栈将其改写成迭代的形式。改写起来也不难，只需要在函数开始执行时压栈（下图左边部分的向下箭头），函数返回时出栈(下图左边部分的向上箭头)即可。下图右边部分对应的是不同阶段栈的情况，读者可以据此来编写基于栈的迭代写法。后面的第113题路径总和II中的迭代写法与之类似，读者只要像这样画出图形，就不难写出代码来。
代码
复杂度分析
● 时间复杂度：在最坏情况下，我们会访问每个节点各一次，时间复杂度为O(n)，其中n是节点个数，但是使用辅助栈来模拟函数调用栈，通常来讲速度是更快的，因为函数调用栈会有一些其他的时间开销，也就是说模拟栈会使时间复杂度的常数系数更小。
● 空间复杂度：空间复杂度和解法一一致。
5.3.2 路径总和II
题目描述（第113题）
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明：叶子节点是指没有子节点的节点。
示例：给定如下二叉树，以及目标和sum=22。
返回[[5,4,11,2]，[5,8,4,5]]。
解法一 DFS递归
思路
由题目可以发现，本题的描述和上一节几乎一模一样。不同的是需要输出所有符合条件的路径，而在5.3.1节中，我们只需要判断是否存在一条符合条件的路径即可。
那么该如何在DFS过程中记录符合条件的路径呢？
可以在DFS过程中多传入一个额外的数组来保存搜索的路径。回溯时有一个需要注意的细节，那就是对路径数组进行撤销的操作，这里可以使用一个小技巧来解决，即在递归调用时使用值传递的方式传递路径数组（而不是直接修改路径数组本身）。
另外，我们需要在递归出口加上保存符合条件路径的操作。
和上一节一样，本题可以分别使用递归和迭代的写法来解决。
代码
复杂度分析
● 时间复杂度：在最坏情况下，我们会访问每个节点各一次，时间复杂度为O(n)，其中n是节点个数。
● 空间复杂度：所需额外的空间和树的高度呈线性关系。在最坏情况下，整个树是非平衡的，每个节点都只有一个子节点，完全变为单链表的形态，此时树的高度是n，因此栈的空间开销是O(n)，但在最好情况下，树是完全平衡的，高度为logn，在这种情况下空间复杂度只有O(logn)。
解法二 DFS迭代
代码
复杂度分析
● 时间复杂度：在最坏情况下，会访问每个节点各一次，时间复杂度为O(n)，其中n是节点个数。
● 空间复杂度：所需额外的空间和树的高度呈线性关系。在最坏情况下，整个树是非平衡的，每个节点都只有一个子节点，完全变为单链表的形态，此时树的高度是n，因此栈的空间开销是O(n)，但在最好情况下，树是完全平衡的，高度为logn，在这种情况下空间复杂度只有O(logn)。
5.3.3 二叉树中的最大路径和
题目描述（第124题）
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发并达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例
输入：[1,2,3]
输出：6
思路
我们知道，树本身是图的一种特例，找树中任意起点的最大路径和其实就是找图中的最大权值和。
我们先思考一种简单的情况——只有3个节点的子树。
它包含的路径和总共有6种。
● b。
● c。
● a。
● a+b。
● a+c。
● b+a+c。
b和c分别是单节点子树的最大值（也就是该节点本身）。
假设上面这个子树是整个树的一部分，那么对于获取最终答案而言，该子树可能的贡献有如下3种情况。
● 整个树的最大路径和就在这个子树当中，不再经过这个子树外的其他节点，则最终结果是
。
➢ 取a表示b和c都无法给最大路径和做贡献，也就是都小于0。
➢ 取b或c与取a类似。
➢ 取a+b+c表示b和c都给最大路径和做贡献，也就是都大于0。
➢ 取a+b表示c无法给最大路径和做贡献，也就是小于0。
➢ 取a+c与a+b类似。
● 最大路径和包含节点a，并且通过a扩展到子树外的其他节点。这里
表示最大路径和中由节点a往外延伸的剩余部分路径和，最终结果是
。
● 不包含子树a。
如果把节点b和c抽象成任意一个子树的左/右子树，我们便可以将子树a的情况扩展到整个树，实现从特例到全局的抽象。遇到这类可以用同种逻辑处理问题及其子问题的情况，使用递归思想是一个不错的思路。
设定一个全局变量存储最大路径和，不断递归搜索每个子树更新该变量。
● 首先搜索的是最左边的最小子树，不断回溯到更大一点的子树，直到root节点的整个左子树被搜索完成。
● 然后对root节点的右子树做同样的操作。
● 最后再判断包含root节点的情况。
由前面的分析可以看出，对于这道题来说，对于树中的任意一个节点，如果知道它子节点的答案，就能计算出当前节点的答案，因此我们使用自底向上的后序遍历来完成。
详细的代码非常简洁、易懂，如下所示。
复杂度分析
● 时间复杂度：因为寻找的是最大路径和，所以我们会访问每个节点各一次，因此时间复杂度为O(n)，其中n是节点个数。
● 空间复杂度：所需额外的空间和树的高度呈线性关系。在最坏情况下，整个树是非平衡的，每个节点都只有一个子节点，完全变为单链表的形态，此时树的高度是n，因此栈的空间开销是O(n)，但在最好情况下，树是完全平衡的，高度为logn，在这种情况下空间复杂度只有O(logn)。