LeetCode题目113:多种算法实现路径总和ll

题目描述

给你一个二叉树和一个目标和 targetSum，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。

示例

输入：

    5
   / \
  4   8
 /   / \
11  13  4
/ \      / \
7   2    5   1

目标和 targetSum = 22

输出：[[5,4,11,2], [5,8,4,5]]

方法一：递归深度优先搜索（DFS）

解题步骤

递归函数定义：定义一个辅助函数来递归检查每个节点，传递当前路径和累积路径列表。
递归终止条件：如果当前节点是叶子节点，并且其值加上累计总和等于目标值，将路径添加到结果列表。
递归逻辑：递归检查当前节点的左右子节点，并更新路径列表和当前和。

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):
    results = []
    
    def dfs(node, current_sum, path):
        if not node:
            return
        current_sum += node.val
        path.append(node.val)
        
        if not node.left and not node.right and current_sum == targetSum:
            results.append(path.copy())  # 注意复制列表
        
        dfs(node.left, current_sum, path)
        dfs(node.right, current_sum, path)
        path.pop()  # 回溯
    
    dfs(root, 0, [])
    return results

算法分析

时间复杂度：(O(n))，每个节点访问一次。
空间复杂度：(O(h))，递归栈的深度，其中 (h) 是树的高度。

方法一使用递归的深度优先搜索（DFS）来寻找所有符合条件的路径。虽然这种方法直观且能有效地解决问题，但它可能会因为大量的递归调用而在空间复杂度上较高，特别是在不平衡的树中。以下是对方法一的几项改进，旨在优化其性能和可读性。

方法一改进：优化的递归DFS

改进点

短路逻辑：一旦达到一个叶子节点并且路径和不符合目标值，立即回溯，减少不必要的递归。
减少中间数组操作：通过直接传递路径而不是在每次递归中创建新的数组拷贝，可以减少内存的使用和可能的垃圾回收。

改进后的 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):
    results = []
    
    def dfs(node, current_sum, path):
        if not node:
            return
        
        # 更新当前路径和
        current_sum += node.val
        # 将当前节点值添加到路径中
        path.append(node.val)
        
        # 检查当前节点是否为叶子节点且路径和是否符合条件
        if not node.left and not node.right:
            if current_sum == targetSum:
                results.append(list(path))  # 添加一份路径的拷贝
        
        # 递归遍历左右子节点
        if node.left:
            dfs(node.left, current_sum, path)
        if node.right:
            dfs(node.right, current_sum, path)
        
        # 回溯，移除当前节点值
        path.pop()

    dfs(root, 0, [])
    return results

算法分析

时间复杂度：优化后，时间复杂度仍为 (O(n))，因为每个节点最多被访问一次。
空间复杂度：优化后的空间复杂度主要取决于递归的深度，最坏情况下为 (O(h))，其中 (h) 是树的高度。使用回溯法避免了不必要的数组拷贝，减少了内存占用。

优劣势比较

优点：
- 减少内存占用，尤其是通过避免不必要的数组拷贝。
- 短路逻辑减少了无效的路径探索，提高了算法效率。
缺点：
- 代码复杂度略有增加，需要仔细管理路径变量和回溯机制。

通过这种改进，递归方法在处理复杂或深度较大的树结构时变得更加高效和稳健。这种优化使得方法既能快速找到解决方案，又能控制内存的使用，适合在资源受限的环境中运行。

方法二：迭代使用栈

解题步骤

使用栈：利用栈存储每个节点及其对应的路径总和和当前路径。
迭代逻辑：迭代访问每个节点，更新路径总和，检查叶子节点的路径总和。

Python 示例

def pathSum(root, targetSum):
    if not root:
        return []
    results = []
    stack = [(root, root.val, [root.val])]
    
    while stack:
        node, curr_sum, path = stack.pop()
        if not node.left and not node.right and curr_sum == targetSum:
            results.append(path)
        if node.right:
            stack.append((node.right, curr_sum + node.right.val, path + [node.right.val]))
        if node.left:
            stack.append((node.left, curr_sum + node.left.val, path + [node.left.val]))
    
    return results

算法分析

时间复杂度：(O(n))，每个节点至多访问一次。
空间复杂度：(O(n))，在最坏的情况下，栈中需要存储所有节点。

优劣势对比

方法	优点	缺点
DFS递归	代码直观易懂；适合复杂树结构	高空间复杂度，依赖于树的高度
迭代使用栈	明确控制遍历过程；适合避免递归引起的问题	空间复杂度较高，代码复杂度高于递归