二叉树路径求和算法与实现详解

1. 二叉树路径求和问题解析

1.1 问题定义与理解

题目"二叉树中和为某一值的路径（一）"要求我们在一棵二叉树中，找出所有从根节点到叶子节点的路径，使得路径上节点值的和等于给定的目标值。这是一个经典的树形结构遍历与回溯问题，在技术面试中频繁出现。

举个例子，假设我们有如下二叉树：

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

当目标值为22时，正确的路径应该是：5→4→11→2

这个问题的难点在于：

1. 需要完整遍历所有可能的路径
2. 必须严格满足从根节点到叶子节点的完整路径
3. 路径求和需要精确匹配目标值

1.2 核心算法思路

解决这类问题的标准方法是深度优先搜索(DFS)配合回溯。具体思路如下：

1. 从根节点开始遍历
2. 记录当前路径和路径节点值的和
3. 当到达叶子节点时，检查路径和是否等于目标值
4. 无论是否匹配，都需要回溯到上一个节点继续搜索

这种方法的优势在于：

• 时间复杂度O(n)，每个节点只访问一次
• 空间复杂度O(h)，h为树的高度，主要是递归栈的开销
• 能够系统地遍历所有可能的路径

2. 递归解法实现细节

2.1 基础递归实现

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

def pathSum(root, targetSum):
    if not root:
        return []
    
    result = []
    
    def dfs(node, current_path, remaining):
        if not node.left and not node.right:  # 叶子节点
            if remaining == 0:
                result.append(current_path.