LeetCode LCR 050. 路径总和 III

Categories:

题目描述
思路分析
1. 解法一：前缀和 + DFS（推荐）
相似题目

题目描述

✅ LCR 050. 路径总和 III

思路分析

解法一：前缀和 + DFS（推荐）

核心思路：

用前缀和统计从根到当前结点的路径和。

若当前前缀和为 sum，则以当前结点为结尾的路径数量为 prefix[sum - target]。

DFS 进入子树时更新前缀和，回溯时恢复计数。

复杂度分析：

时间复杂度：O(n)，其中 n 为结点数量。

空间复杂度：O(n)，哈希表与递归栈占用。

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefix = new HashMap<>();
        prefix.put(0L, 1);
        return dfs(root, 0L, targetSum, prefix);
    }

    private int dfs(TreeNode node, long cur, int target, Map<Long, Integer> prefix) {
        if (node == null) {
            return 0;
        }

        cur += node.val;

        int count = prefix.getOrDefault(cur - target, 0);

        // 进入子树前更新当前前缀和计数
        prefix.put(cur, prefix.getOrDefault(cur, 0) + 1);
        count += dfs(node.left, cur, target, prefix);
        count += dfs(node.right, cur, target, prefix);
        prefix.put(cur, prefix.get(cur) - 1);

        return count;
    }
}

func pathSum(root *TreeNode, targetSum int) int {
    prefix := map[int64]int{0: 1}

    var dfs func(node *TreeNode, cur int64) int
    dfs = func(node *TreeNode, cur int64) int {
        if node == nil {
            return 0
        }

        cur += int64(node.Val)
        count := prefix[cur-int64(targetSum)]

        // 进入子树前更新当前前缀和计数
        prefix[cur]++
        count += dfs(node.Left, cur)
        count += dfs(node.Right, cur)
        prefix[cur]--

        return count
    }

    return dfs(root, 0)
}

相似题目

题目	难度	考察点
560. 和为 K 的子数组	中等	前缀和
112. 路径总和	简单	DFS
113. 路径总和 II	中等	DFS
124. 二叉树中的最大路径和	困难	DFS
129. 求根到叶子节点数字之和	中等	DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/35331271