LeetCode 路径总和 III：从暴力到优化的深度剖析

在 LeetCode 上，路径总和 III (437) 是一道经典的二叉树问题，其核心在于寻找二叉树中所有节点到节点的路径，其路径上的节点值之和等于给定的目标值 targetSum。初见此题，很多开发者会陷入递归的泥潭，写出效率低下的暴力解法。本文将从问题场景出发，深入分析底层原理，并提供多种优化方案，最终给出高效的解决方案。

问题场景重现

给定一个二叉树的根节点 root 和一个整数 targetSum ，请找出该二叉树内有多少路径上的节点值之和等于 targetSum 。

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

示例：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，它们是：
1.  5 -> 3
2.  5 -> 2 -> 1
3. 3 -> 5

暴力解法及其弊端

最直观的解法是从每个节点出发，递归地向下寻找满足条件的路径。这种方法的时间复杂度为 O(N^2)，其中 N 是二叉树的节点数。当二叉树退化成链表时，时间复杂度会变为 O(N^2)。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        if not root:
            return 0
        
        # 从当前节点出发的路径数量 + 左子树的路径数量 + 右子树的路径数量
        return self.pathSumFrom(root, targetSum) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum)

    def pathSumFrom(self, node: TreeNode, targetSum: int) -> int:
        if not node:
            return 0

        count = 0
        if node.val == targetSum:
            count += 1

        count += self.pathSumFrom(node.left, targetSum - node.val)
        count += self.pathSumFrom(node.right, targetSum - node.val)

        return count

这种解法的效率瓶颈在于大量的重复计算。例如，从根节点向下搜索时，很多路径会被重复计算多次。

前缀和优化：空间换时间

为了避免重复计算，可以使用前缀和的思想进行优化。前缀和是指从根节点到当前节点的路径上所有节点值的和。我们可以使用一个哈希表来记录每个前缀和出现的次数。在遍历二叉树的过程中，维护当前节点的前缀和，并在哈希表中查找是否存在 prefixSum - targetSum 的前缀和。如果存在，则说明从根节点到当前节点的路径上存在一段路径的和等于 targetSum。

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        prefix_sum = {0: 1}  # 初始化前缀和哈希表，和为 0 的路径有 1 条（空路径）
        
        def dfs(node: TreeNode, current_sum: int) -> int:
            if not node:
                return 0

            current_sum += node.val  # 更新当前前缀和
            count = prefix_sum.get(current_sum - targetSum, 0)  # 查找是否存在满足条件的前缀和

            prefix_sum[current_sum] = prefix_sum.get(current_sum, 0) + 1  # 更新前缀和哈希表

            count += dfs(node.left, current_sum)
            count += dfs(node.right, current_sum)

            prefix_sum[current_sum] -= 1  # 回溯，恢复前缀和哈希表
            return count

        return dfs(root, 0)

这种解法的时间复杂度为 O(N)，空间复杂度为 O(N)。利用了哈希表快速查找的特性，避免了大量的重复计算。在实际应用中，如果二叉树的深度较大，可以考虑使用非递归的方式实现深度优先搜索，以避免栈溢出的风险。

实战避坑经验总结

1. 前缀和哈希表的初始化： 一定要初始化 prefix_sum[0] = 1，表示从根节点开始的空路径和为 0，且存在一条这样的路径。
2. 回溯： 在递归返回时，一定要恢复前缀和哈希表的状态，避免影响其他路径的计算。
3. 数据类型溢出： 在计算前缀和时，需要注意数据类型溢出的问题。如果节点值较大，可以考虑使用 long 类型存储前缀和。
4. 测试用例覆盖： 在测试时，需要覆盖各种边界情况，例如空树、只有一个节点的树、所有节点值都为 0 的树等。

扩展思考：高并发场景下的优化

如果在高并发场景下，需要频繁地查询二叉树的路径总和，可以考虑使用缓存技术来提高查询效率。例如，可以使用 Redis 或 Memcached 等缓存服务器来缓存二叉树的结构和前缀和信息。同时，可以使用 Nginx 作为反向代理服务器，对请求进行负载均衡，提高系统的并发处理能力。此外，可以使用宝塔面板等工具简化服务器的运维工作。

在高并发场景下，还需要考虑并发连接数的问题。可以通过调整 Nginx 的配置参数，例如 worker_connections 和 keepalive_timeout，来优化并发连接数。