24 二叉树中和为某一值的路径

题目描述

输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

示例：

树:
       10
      /  \
     5    12
    / \
   4   7

目标值: 22
输出: [[10, 5, 7], [10, 12]]

解题思路

核心思想：使用回溯法，DFS遍历所有路径。

关键步骤：

1. 将当前节点加入路径
2. 计算当前路径的和
3. 如果是叶子节点且和等于目标值，记录该路径
4. 递归遍历左子树和右子树
5. 回溯：移除当前节点

时间复杂度：O(n) 空间复杂度：O(n)

Python 实现

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


def find_path(root, target):
    """
    找出二叉树中和为目标值的所有路径

    Args:
        root: 二叉树根节点
        target: 目标和

    Returns:
        list: 所有满足条件的路径
    """
    result = []
    path = []

    def dfs(node, current_sum):
        if not node:
            return

        # 加入当前节点
        path.append(node.val)
        current_sum += node.val

        # 如果是叶子节点且和等于目标值
        if not node.left and not node.right and current_sum == target:
            result.append(path[:])

        # 递归遍历子树
        dfs(node.left, current_sum)
        dfs(node.right, current_sum)

        # 回溯
        path.pop()

    dfs(root, 0)
    return result


# 测试代码
if __name__ == "__main__":
    # 创建树:
    #        10
    #       /  \
    #      5    12
    #     / \
    #    4   7
    root = TreeNode(10)
    root.left = TreeNode(5)
    root.right = TreeNode(12)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(7)

    print("目标和为22的路径:", find_path(root, 22))
    # 输出: [[10, 5, 7], [10, 12]]

    print("目标和为15的路径:", find_path(root, 15))
    # 输出: [[10, 5]]

图解

树:
       10
      /  \
     5    12
    / \
   4   7

DFS遍历过程:

路径: [10], sum=10
  → 左: [10,5], sum=15
      → 左: [10,5,4], sum=19 (叶子, 不匹配)
      → 右: [10,5,7], sum=22 (叶子, 匹配!) 记录
  → 右: [10,12], sum=22 (叶子, 匹配!) 记录

结果: [[10, 5, 7], [10, 12]]