二叉树路径求和问题解析与LeetCode解题技巧

1. 二叉树路径问题概述

在算法面试和日常编程中，二叉树路径求和问题堪称经典中的经典。这类问题看似简单，实则暗藏玄机，能够全面考察程序员对递归、回溯、树遍历等基础算法的掌握程度。最近我在准备面试和刷题过程中，系统梳理了LeetCode上路径之和系列的三道题目（112/113/437），发现它们呈现明显的递进关系，非常适合作为算法进阶的阶梯式训练。

这三道题虽然核心都是"路径求和"，但考察重点各有不同：

• 路径总和I（112题）：判断是否存在满足条件的路径
• 路径总和II（113题）：找出所有满足条件的路径
• 路径总和III（437题）：统计满足条件的路径数量（路径可不从根节点开始）

2. 基础问题解析：路径总和I（LeetCode 112）

2.1 问题描述与示例

给定一个二叉树和一个目标和，判断该树中是否存在从根节点到叶子节点的路径，使得路径上所有节点值相加等于目标和。

示例：

code复制      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

目标和=22，返回true，因为存在路径5→4→11→2，其和为22。

2.2 递归解法实现

这是最直观的解法，时间复杂度O(n)，空间复杂度O(h)（h为树高）：

python复制def hasPathSum(root, targetSum):
    if not root:
        return False
    if not root.left and not root.right:  # 叶子节点
        return root.val == targetSum
    return hasPathSum(root.left, targetSum - root.val) or \
           hasPathSum(root.right, targetSum - root.val)

2.3 迭代解法与注意事项

使用栈实现DFS迭代：

python复制def hasPathSum(root, targetSum):
    if not root:
        return False
    stack = [(root, targetSum - root.val)]
    while stack:
        node, curr_sum = stack.pop()
        if not node.left and not node.right and curr_sum == 0:
            return True
        if node.right:
            stack.append((node.right, curr_sum - node.right.val))
        if node.left:
            stack.append((node.left, curr_sum - node.left.val))
    return False

注意：迭代实现时要注意入栈顺序，因为栈是LIFO结构，如果想保持和递归相同的遍历顺序（如先左后右），需要先将右子节点入栈。

3. 进阶问题：路径总和II（LeetCode 113）

3.1 问题升级点

在I的基础上，不仅需要判断是否存在路径，还要找出所有满足条件的路径。这要求我们在递归过程中维护当前路径。

3.2 回溯解法实现

时间复杂度O(n^2)（最坏情况下所有路径都符合条件），空间复杂度O(n)：

python复制def pathSum(root, targetSum):
    def backtrack(node, remain, path, res):
        if not node:
            return
        path.append(node.val)
        if not node.left and not node.right and remain == node.val:
            res.append(list(path))
        backtrack(node.left, remain - node.val, path, res)
        backtrack(node.right, remain - node.val, path, res)
        path.pop()  # 关键回溯步骤
    
    result = []
    backtrack(root, targetSum, [], result)
    return result

3.3 性能优化技巧

1. 使用双端队列代替列表可以提高pop()操作的效率
2. 对于大型树，可以考虑迭代实现避免递归栈溢出
3. 提前终止条件：当当前路径和已经超过targetSum时（假设所有节点值为正数）

4. 高阶问题：路径总和III（LeetCode 437）

4.1 问题复杂化

路径不需要从根节点开始，也不需要在叶子节点结束，但必须是从父节点到子节点的向下路径。这使得问题难度陡然提升。

示例：

code复制      10
     /  \
    5    -3
   / \    \
  3   2   11
 / \   \
3  -2   1

targetSum=8，返回3。存在的路径有：

1. 5 → 3
2. 5 → 2 → 1
3. -3 → 11

4.2 前缀和解法

这是最优解法，时间复杂度O(n)，空间复杂度O(n)：

python复制from collections import defaultdict

def pathSum(root, targetSum):
    prefix = defaultdict(int)
    prefix[0] = 1  # 初始状态：和为0出现1次
    
    def dfs(node, curr_sum):
        if not node:
            return 0
        curr_sum += node.val
        res = prefix.get(curr_sum - targetSum, 0)
        prefix[curr_sum] += 1
        res += dfs(node.left, curr_sum)
        res += dfs(node.right, curr_sum)
        prefix[curr_sum] -= 1  # 回溯
        return res
    
    return dfs(root, 0)

4.3 双重递归解法

虽然时间复杂度O(n^2)较高，但更易理解：

python复制def pathSum(root, targetSum):
    if not root:
        return 0
    return (dfs(root, targetSum) + 
            pathSum(root.left, targetSum) + 
            pathSum(root.right, targetSum))

def dfs(node, remain):
    if not node:
        return 0
    remain -= node.val
    return (1 if remain == 0 else 0) + \
           dfs(node.left, remain) + \
           dfs(node.right, remain)

5. 系列问题对比与总结

5.1 解题思路演进

5.2 通用优化策略

1. 剪枝优化：在递归过程中，如果确定后续分支不可能满足条件，提前终止递归
2. 记忆化：对于重复计算的子问题，使用哈希表存储中间结果
3. 迭代转化：对于深度较大的树，将递归改为迭代避免栈溢出

5.3 常见错误与调试技巧

1. 路径总和II中容易忘记回溯时的pop()操作，导致路径错误
2. 路径总和III的前缀和解法中，哈希表的初始状态(prefix[0]=1)容易被忽略
3. 所有问题都要注意处理空树和单节点树的边界情况

在实际面试中，面试官常常会从最简单的路径总和I开始，逐步追问更复杂的变种。理解这三道题的内在联系，掌握从简单递归到前缀和优化的演进思路，能够展现出扎实的算法基础和系统性的思考能力。