这一节，我们将介绍更复杂的 recursion。

例：LeetCode 第 437 题：路径总和 III

传送门：437. 路径总和 III。

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例：

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3。和等于 8 的路径有:

1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

分析：这道题与之前的 Path Sum 不同的地方在于：不一定起始于跟结点，终于叶子结点。
之前的 Path Sum 逻辑默认了一件事情，那就是递归过程中的 node 结点一定在所求的路径中，即 node 结点充当了路径的一部分。所以接下来我们要分情况讨论。

• pathSum
• findPath

这里要画一些示意图帮助我们解决这个问题。

难点：

1. 两层递归函数。
   分析递归关系：针对每一个结点寻找的路径的个数由三个部分组成：

• 包含自己
• 不包含自己，在左子树中寻找
• 不包含自己，在右子树中寻找

2. 我们自己定义的递归函数的定义很重要。

关键：还是发现递归关系，这里的递归关系，就是包含 root 结点和不包含根结点的解数之和，就是我们要求的。（通过这一道题的解法，可以让我们进一步理解递归方法的威力。）

Python 代码：

# 437. 路径总和 III
# 给定一个二叉树，它的每个结点都存放着一个整数值。
#
# 找出路径和等于给定数值的路径总数。
#
# 路径不需要从根结点开始，也不需要在叶子结点结束，但是路径方向必须是向下的（只能从父结点到子结点）。
#
# 二叉树不超过1000个结点，且结点数值范围是 [-1000000,1000000] 的整数。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# 这个解答来自评论区，暂时没有看懂

class Solution:
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        from collections import defaultdict
        memo = defaultdict(int)
        # 记忆化递归，memo 表示缓存
        memo[0] = 1  # 表示 cur - sum = 0, return 1
        self.res = 0

        def helper(root, curSum):
            if root is None:
                return
            curSum += root.val
            self.res += memo[curSum - sum]
            memo[curSum] += 1

            helper(root.left, curSum)
            helper(root.right, curSum)
            memo[curSum] -= 1

        helper(root, 0)
        return self.res

Java 代码：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

// https://leetcode-cn.com/problems/path-sum-iii/description/

public class Solution {

    private int dfs(TreeNode root, int sum) {
        int result = 0;
        if (root == null) {
            return 0;
        }
        if (root.val == sum) {
            // 后面的满足条件的路径之和为 0
            result++;
        }
        result += dfs(root.left, sum - root.val);
        result += dfs(root.right, sum - root.val);
        return result;
    }

    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        return dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }

}

（本节完）