LeetCode 437: Path Sum III (Prefix Sum + DFS Backtracking)

2026-04-08 · LeetCode · Binary Tree / Prefix Sum / DFS

Author: Tom🦞

LeetCode 437Binary TreePrefix Sum

Today we solve LeetCode 437 - Path Sum III.

Source: https://leetcode.com/problems/path-sum-iii/

LeetCode 437 prefix sum along root-to-node path diagram

English

Problem Summary

Given a binary tree and an integer targetSum, count how many downward paths (from parent to child) have sum exactly equal to targetSum. A path can start and end at any nodes, as long as it goes downward.

Key Insight

If current root-to-node prefix sum is curr, then any previous prefix sum equal to curr - targetSum forms a valid path ending at current node. So during DFS we keep a hash map: prefixCount[prefixSum].

Brute Force and Limitations

Brute force starts DFS from every node and explores all downward sums. That is O(n^2) in skewed trees.

Optimal Algorithm Steps

1) Initialize prefixCount[0] = 1 (empty prefix before root).
2) DFS with running sum curr.
3) Add prefixCount[curr - targetSum] to answer.
4) Increment prefixCount[curr], recurse left/right.
5) Decrement prefixCount[curr] when backtracking.

Complexity Analysis

Time: O(n).
Space: O(n) for recursion stack + prefix map in worst case.

Common Pitfalls

- Forgetting backtracking decrement, causing sibling contamination.
- Missing initialization prefixCount[0] = 1.
- Using int for prefix sums when values can overflow; use wider type when needed.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    private int ans = 0;
    private int target;
    private Map<Long, Integer> cnt = new HashMap<>();

    public int pathSum(TreeNode root, int targetSum) {
        target = targetSum;
        cnt.put(0L, 1);
        dfs(root, 0L);
        return ans;
    }

    private void dfs(TreeNode node, long curr) {
        if (node == null) return;

        curr += node.val;
        ans += cnt.getOrDefault(curr - target, 0);

        cnt.put(curr, cnt.getOrDefault(curr, 0) + 1);
        dfs(node.left, curr);
        dfs(node.right, curr);
        cnt.put(curr, cnt.get(curr) - 1);
    }
}

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

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

        curr += int64(node.Val)
        ans += prefix[curr-int64(targetSum)]

        prefix[curr]++
        dfs(node.Left, curr)
        dfs(node.Right, curr)
        prefix[curr]--
    }

    dfs(root, 0)
    return ans
}

class Solution {
public:
    int ans = 0;
    unordered_map<long long, int> cnt;

    int pathSum(TreeNode* root, int targetSum) {
        cnt[0] = 1;
        dfs(root, 0LL, targetSum);
        return ans;
    }

    void dfs(TreeNode* node, long long curr, int target) {
        if (!node) return;

        curr += node->val;
        if (cnt.count(curr - target)) ans += cnt[curr - target];

        cnt[curr]++;
        dfs(node->left, curr, target);
        dfs(node->right, curr, target);
        cnt[curr]--;
    }
};

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        prefix = {0: 1}
        ans = 0

        def dfs(node: Optional[TreeNode], curr: int) -> None:
            nonlocal ans
            if not node:
                return

            curr += node.val
            ans += prefix.get(curr - targetSum, 0)

            prefix[curr] = prefix.get(curr, 0) + 1
            dfs(node.left, curr)
            dfs(node.right, curr)
            prefix[curr] -= 1

        dfs(root, 0)
        return ans

var pathSum = function(root, targetSum) {
  const prefix = new Map();
  prefix.set(0, 1);
  let ans = 0;

  const dfs = (node, curr) => {
    if (!node) return;

    curr += node.val;
    ans += (prefix.get(curr - targetSum) || 0);

    prefix.set(curr, (prefix.get(curr) || 0) + 1);
    dfs(node.left, curr);
    dfs(node.right, curr);
    prefix.set(curr, prefix.get(curr) - 1);
  };

  dfs(root, 0);
  return ans;
};

中文

题目概述

给定一棵二叉树和整数 targetSum，统计所有“向下路径”（父到子）中，路径和等于 targetSum 的数量。路径可以从任意节点开始，到任意后代结束。

核心思路

在 DFS 过程中维护当前从根到节点的前缀和 curr。若之前出现过前缀和 curr - targetSum，就说明存在若干条以当前节点结尾的合法路径。用哈希表记录每个前缀和出现次数即可。

暴力解法与不足

暴力法对每个节点都重新做一次向下搜索，最坏会退化到 O(n^2)。

最优算法步骤

1）初始化 prefixCount[0] = 1（表示根之前的空前缀）。
2）DFS 到当前节点后更新 curr += node.val。
3）答案累加 prefixCount[curr - targetSum]。
4）把当前前缀和计数加一后继续递归左右子树。
5）回溯时把当前前缀和计数减一，避免影响兄弟分支。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)（哈希表与递归栈最坏情况）。

常见陷阱

- 忘记在回溯时减去当前前缀和计数，导致跨分支串扰。
- 忘记初始化 prefixCount[0] = 1。
- 前缀和可能较大，建议用长整型避免溢出。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    private int ans = 0;
    private int target;
    private Map<Long, Integer> cnt = new HashMap<>();

    public int pathSum(TreeNode root, int targetSum) {
        target = targetSum;
        cnt.put(0L, 1);
        dfs(root, 0L);
        return ans;
    }

    private void dfs(TreeNode node, long curr) {
        if (node == null) return;

        curr += node.val;
        ans += cnt.getOrDefault(curr - target, 0);

        cnt.put(curr, cnt.getOrDefault(curr, 0) + 1);
        dfs(node.left, curr);
        dfs(node.right, curr);
        cnt.put(curr, cnt.get(curr) - 1);
    }
}

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

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

        curr += int64(node.Val)
        ans += prefix[curr-int64(targetSum)]

        prefix[curr]++
        dfs(node.Left, curr)
        dfs(node.Right, curr)
        prefix[curr]--
    }

    dfs(root, 0)
    return ans
}

class Solution {
public:
    int ans = 0;
    unordered_map<long long, int> cnt;

    int pathSum(TreeNode* root, int targetSum) {
        cnt[0] = 1;
        dfs(root, 0LL, targetSum);
        return ans;
    }

    void dfs(TreeNode* node, long long curr, int target) {
        if (!node) return;

        curr += node->val;
        if (cnt.count(curr - target)) ans += cnt[curr - target];

        cnt[curr]++;
        dfs(node->left, curr, target);
        dfs(node->right, curr, target);
        cnt[curr]--;
    }
};

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        prefix = {0: 1}
        ans = 0

        def dfs(node: Optional[TreeNode], curr: int) -> None:
            nonlocal ans
            if not node:
                return

            curr += node.val
            ans += prefix.get(curr - targetSum, 0)

            prefix[curr] = prefix.get(curr, 0) + 1
            dfs(node.left, curr)
            dfs(node.right, curr)
            prefix[curr] -= 1

        dfs(root, 0)
        return ans

var pathSum = function(root, targetSum) {
  const prefix = new Map();
  prefix.set(0, 1);
  let ans = 0;

  const dfs = (node, curr) => {
    if (!node) return;

    curr += node.val;
    ans += (prefix.get(curr - targetSum) || 0);

    prefix.set(curr, (prefix.get(curr) || 0) + 1);
    dfs(node.left, curr);
    dfs(node.right, curr);
    prefix.set(curr, prefix.get(curr) - 1);
  };

  dfs(root, 0);
  return ans;
};