目录

437. 路径总和 III

深度优先遍历

前缀和优化

124. 二叉树中的最大路径和 

---

437. 路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

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

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

提示:

• 二叉树的节点个数的范围是 [0,1000]
• -109 <= Node.val <= 109 
• -1000 <= targetSum <= 1000 

深度优先遍历

1. rootSum 方法：这个方法计算从当前节点 root 开始，所有路径上节点值之和等于 targetSum 的路径数量。它会递归地考虑以 root 为起点，向下延伸到左子树和右子树的所有路径。

2. pathSum 方法：这个方法不仅仅考虑以根节点为起点的路径，还递归地对树中的每个节点调用自身，相当于把每个节点都当作一次新的根节点来进行计算。它会递归地调用 rootSum 方法来计算从每个节点开始的路径数量。

这里的关键在于，rootSum 方法只计算从特定的起点（当前节点）开始的路径数量，而 pathSum 方法会对树中的每个节点都调用 rootSum 方法，这样就能覆盖从树中的每个节点开始的所有可能路径。

所以，pathSum(root, targetSum) 的第一次调用 rootSum(root, targetSum) 计算的是从根节点开始的所有路径，而接下来的两次递归调用 pathSum(root.left, targetSum) 和 pathSum(root.right, targetSum) 则是分别计算从左子树和右子树的每个节点开始的所有路径。

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = rootSum(root, targetSum);
        ret += pathSum(root.left, targetSum);
        ret += pathSum(root.right, targetSum);
        return ret;
    }

    public int rootSum(TreeNode root, int targetSum) {
        int ret = 0;

        if (root == null) {
            return 0;
        }
        int val = root.val;
        if (val == targetSum) {
            ret++;
        } 

        ret += rootSum(root.left, targetSum - val);
        ret += rootSum(root.right, targetSum - val);
        return ret;
    }
}

前缀和优化

解法一中应该存在许多重复计算，我们现在定义：前缀和是一个数列的每一项索引从0开始，表示从第0项到当前项的和。在这个问题中，我们将前缀和应用于二叉树的路径上，即从根节点到当前节点的所有节点值的和。

1. 初始化：创建一个哈希表 prefix 来保存前缀和及其出现次数。为了处理从根节点开始的路径，我们提前在哈希表中设置前缀和0的计数为1。

2. 递归遍历：dfs 函数返回的是从当前节点 root 出发的，路径和等于 targetSum 的路径数量。

3. 查找当前路径和：检查当前的前缀和减去 targetSum 的结果是否在之前的路径中已经出现过，也就是检查 curr - targetSum 是否在哈希表 prefix 中。如果是，说明存在一个子路径的和等于 targetSum，将对应的次数添加到结果中。

4. 更新哈希表：在访问节点之前，将当前前缀和的计数增加1，以表示这个前缀和现在被包含在路径中。

5. 递归子节点：继续对左右子节点进行相同的处理。

6. 回溯：在返回之前，需要将当前节点的前缀和的计数减1，因为当前节点即将被回溯，不应该计入其他路径（回溯保证了，哈希表里存储的始终是从根节点到当前节点的方向上所有路径的前缀和）。

class Solution {
    // 主函数
    public int pathSum(TreeNode root, int targetSum) {
        // 哈希表用于存储所有前缀和及其出现次数
        Map<Long, Integer> prefix = new HashMap<Long, Integer>();
        // 初始化：前缀和为0的路径有1条（空路径）
        prefix.put(0L, 1);
        // 开始深度优先搜索
        return dfs(root, prefix, 0, targetSum);
    }

    // 辅助函数：深度优先搜索
    public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
        // 如果当前节点为空，则返回0，表示没有路径
        if (root == null) {
            return 0;
        }

        int ret = 0; // 用于记录路径数
        curr += root.val; // 更新当前路径和

        // 查找当前路径和减去目标值的结果是否在前缀和中出现过
        // 出现过则表示找到了一条路径
        ret = prefix.getOrDefault(curr - targetSum, 0);

        // 更新前缀和中当前路径和的计数
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);

        // 递归地搜索左子树和右子树，并累加路径数
        ret += dfs(root.left, prefix, curr, targetSum);
        ret += dfs(root.right, prefix, curr, targetSum);

        // 是不是要回溯，取决于“我有没有改了外部（共享的）状态，并且这个状态会影响后续的兄弟分支”。
        // 回溯：在返回之前，将当前节点的路径和的计数减1
        // 因为当前节点即将被回溯，不应该计入其他路径
        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);

        // 返回找到的路径总数
        return ret;
    }
}

让我们通过一个具体的例子来说明回溯在前缀和算法中的应用。假设有以下二叉树：

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

并且我们要找的 targetSum 是8。我们将按照前缀和算法遍历这棵树。

1. 开始于根节点 (10):

   • 当前前缀和: curr = 10
   • prefix = { (0,1) } （初始化，路径和为0出现了1次）

2. 移动到左子节点 (5):

   • 当前前缀和: curr = 15
   • 更新前缀和计数: prefix = { (0,1), (15,1) }

3. 继续到该节点的左子节点 (3):

   • 当前前缀和: curr = 18
   • 更新前缀和计数: prefix = { (0,1), (15,1), (18,1) }

4. 进一步到该节点的左子节点 (3):

   • 当前前缀和: curr = 21
   • 更新前缀和计数: prefix = { (0,1), (15,1), (18,1), (21,1) }

5. 回溯到节点 (3) 父节点 (3)：

   • 我们完成了节点 (3) 的所有子节点的遍历
   • 当前前缀和: curr = 18
   • 回溯：prefix = { (0,1), (15,1), (18,1) }，移除之前节点 (3) 的前缀和

6. 遍历节点 (3) 的右子节点 (-2):

   • 当前前缀和: curr = 16
   • 更新前缀和计数: prefix = { (0,1), (15,1), (18,1), (16,1) }
   • 回溯：prefix = { (0,1), (15,1), (18,1) }，完成节点 (-2) 的遍历，移除它的前缀和

7. 回溯到节点 (5) 并转向它的右子节点 (2):

   • 我们完成了节点 (5) 的左子树的遍历
   • 当前前缀和: curr = 15
   • 回溯：prefix = { (0,1), (15,1) }，移除之前节点 (3) 和 (-2) 的前缀和
   • 当前前缀和: curr = 17 (添加节点 (2))
   • 更新前缀和计数: prefix = { (0,1), (15,1), (17,1) }
   • 检查：17 (当前前缀和) - 8 (targetSum) = 9，在 prefix 中没有 9，所以没有发现新路径
   • 遍历节点 (2) 的左子节点 (1)
   • 当前前缀和: curr = 18 (添加节点 (1))
   • 更新前缀和计数: prefix = { (0,1), (15,1), (17,1), (18,1) }
   • 检查：18 (当前前缀和) - 8 (targetSum) = 10，在 prefix 中有 10（根节点的值），所以我们找到了一条路径: 10 → 5 → 2 → 1
   • 回溯：完成节点 (1) 的遍历，回溯节点 (2)

8. 最终回溯到根节点 (10) 并转向它的右子节点 (-3):

   • 当前前缀和: curr = 10
   • 回溯：prefix = { (0,1) }，移除左子树的前

124. 二叉树中的最大路径和 

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

• 树中节点数目范围是 [1, 3 * 104]
• -1000 <= Node.val <= 1000

maxGain 函数的返回值是给定节点 node 对其父节点路径的最大贡献值。

class Solution {
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }


    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;

        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);

        // maxGain 函数返回 node.val + Math.max(leftGain, rightGain) 表示如果当前节点要                    
        //作为其父节点路径的一部分，它能提供的最大贡献。这确保了当递归回溯到父节点时，能够构成有效的路径。
        return node.val + Math.max(leftGain, rightGain);
    }
}