深入剖析 LeetCode 437：路径总和 III 的高效解法与优化技巧

在二叉树中寻找路径和等于给定数值的所有路径，这是一个经典的问题。LeetCode 上的第 437 题，路径总和 III，要求我们找出二叉树中节点值之和等于目标值的路径数量。路径不需要从根节点开始，也不需要在叶节点结束，但是路径必须是向下（只能从父节点到子节点）。 例如，一个简单的二叉树，目标值为 8，就可能存在多条满足条件的路径。

底层原理深度剖析：前缀和与递归

解决这个问题的核心在于高效地计算从任意节点到当前节点路径上所有节点的和。一种常见的，但效率较低的暴力方法是，对每个节点，都递归地向上寻找所有可能的路径。这种方法的时间复杂度会达到 O(N^2)，N 是节点的数量。更优的方案是使用前缀和的思想，结合递归进行求解。

前缀和的概念

所谓前缀和，就是记录从根节点到当前节点路径上的所有节点值的和。当我们遍历到某个节点时，可以利用这个前缀和，快速判断是否存在从之前的某个节点到当前节点，路径和等于目标值的路径。

递归与回溯

我们使用递归来遍历二叉树的每个节点。在递归的过程中，维护一个哈希表，存储到当前节点为止的所有前缀和以及出现的次数。对于每个节点，我们检查从根节点到当前节点的路径上，是否存在一段路径的和等于目标值。如果在哈希表中存在 prefixSum - targetSum，就说明存在一条满足条件的路径。 递归完成后，我们需要进行回溯，将当前节点的前缀和从哈希表中移除，保证不影响其他路径的计算。

代码/配置解决方案：Java 实现 LeetCode 437

import java.util.HashMap;

public class PathSumIII {

    public int pathSum(TreeNode root, int targetSum) {
        HashMap<Integer, Integer> prefixSumCount = new HashMap<>();
        prefixSumCount.put(0, 1); // 初始化，空路径和为 0 出现一次
        return recursionPathSum(root, targetSum, 0, prefixSumCount);
    }

    private int recursionPathSum(TreeNode node, int targetSum, int currentPathSum, HashMap<Integer, Integer> prefixSumCount) {
        if (node == null) {
            return 0;
        }

        // 1.更新当前路径的前缀和
        currentPathSum += node.val;

        // 2.查找是否存在满足条件的路径
        int count = prefixSumCount.getOrDefault(currentPathSum - targetSum, 0);

        // 3.更新前缀和哈希表
        prefixSumCount.put(currentPathSum, prefixSumCount.getOrDefault(currentPathSum, 0) + 1);

        // 4.递归遍历左右子树
        count += recursionPathSum(node.left, targetSum, currentPathSum, prefixSumCount);
        count += recursionPathSum(node.right, targetSum, currentPathSum, prefixSumCount);

        // 5.回溯，移除当前节点的前缀和，避免影响其他路径的计算
        prefixSumCount.put(currentPathSum, prefixSumCount.get(currentPathSum) - 1);

        return count;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}

代码解释

• pathSum(TreeNode root, int targetSum)：主函数，初始化前缀和哈希表，并调用递归函数。
• recursionPathSum(TreeNode node, int targetSum, int currentPathSum, HashMap<Integer, Integer> prefixSumCount)：递归函数，用于遍历二叉树，计算路径和。
• 在递归过程中，首先更新当前路径的前缀和，然后在前缀和哈希表中查找是否存在满足条件的路径。如果存在，则累加到结果中。最后，递归遍历左右子树，并在回溯时移除当前节点的前缀和。

实战避坑经验总结

1. 空指针检查：在递归函数中，一定要首先检查节点是否为空，避免空指针异常。
2. 哈希表初始化：前缀和哈希表需要初始化一个键值对 (0, 1)，表示空路径的和为 0，出现一次。这处理了从根节点开始的路径。
3. 回溯操作：在递归完成后，一定要进行回溯操作，将当前节点的前缀和从哈希表中移除，避免影响其他路径的计算。 这也是使用前缀和解决路径总和 III问题的关键点。
4. 数据溢出：如果节点值较大，可能导致前缀和溢出。需要考虑使用 long 类型存储前缀和，或者使用取模运算。
5. 边界条件：仔细考虑边界条件，例如二叉树为空，目标值为 0 等情况。

这个解法的时间复杂度是 O(N)，空间复杂度是 O(N)。与暴力解法相比，效率有了显著提升。