二叉树路径和问题中的递归逻辑错误输出

二叉树路径和问题通常是指在给定的二叉树中寻找所有从根节点到叶子节点的路径，使得路径上的节点值之和等于给定的目标值。递归是解决这类问题的常用方法，但如果递归逻辑出现错误，可能会导致不正确的输出。

基础概念

二叉树是一种树形数据结构，每个节点最多有两个子节点，通常称为左子节点和右子节点。路径和问题要求找到所有满足特定条件的路径。

递归逻辑错误

递归逻辑错误可能包括但不限于以下几种情况：

基本情况处理不当：例如，没有正确处理空节点的情况。
递归调用参数错误：传递给递归调用的参数不正确，导致计算错误。
累加逻辑错误：在递归过程中，节点值的累加方式不正确。
路径记录错误：在递归过程中，路径的记录方式不正确。

示例代码及错误分析

以下是一个常见的递归实现，假设我们有一个二叉树节点的定义如下：

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

错误的递归实现可能如下：

def pathSum(root, targetSum):
    def dfs(node, currentSum, path):
        if not node:
            return []
        currentSum += node.val
        path.append(node.val)
        if not node.left and not node.right and currentSum == targetSum:
            return [path]
        return dfs(node.left, currentSum, path) + dfs(node.right, currentSum, path)
    
    return dfs(root, 0, [])

这个实现的问题在于路径的记录方式不正确。每次递归调用都会修改同一个路径列表 path，导致最终结果中所有路径都是相同的。

正确的递归实现

正确的实现应该在每次递归调用时传递一个新的路径列表：

def pathSum(root, targetSum):
    def dfs(node, currentSum, path):
        if not node:
            return []
        currentSum += node.val
        new_path = path + [node.val]
        if not node.left and not node.right and currentSum == targetSum:
            return [new_path]
        left_paths = dfs(node.left, currentSum, new_path)
        right_paths = dfs(node.right, currentSum, new_path)
        return left_paths + right_paths
    
    return dfs(root, 0, [])