437. 路径总和 III

题目描述

输入二叉树的根节点 root 和整数 targetSum。二叉树用层序数组表示，空位写 null。

这里的路径指从某个节点出发、每一步都走向子节点所经过的一串节点。起点不必是根，终点也不必是叶子，但方向只能自上而下。

统计节点值之和恰好等于 targetSum 的路径共有多少条，并返回这个数目。

示例 1

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3

解释：和为 8 的路径有 5→3、5→2→1、-3→11，共 3 条。

示例 2

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

解释：和为 22 的路径有 5→4→11→2、5→8→4→5、4→11→7，共 3 条。

数据范围

节点个数在 [0, 1000] 范围内。
-10^9 <= Node.val <= 10^9
-1000 <= targetSum <= 1000

解题思路：前缀和 + 哈希表

深度优先遍历维护当前根路径的前缀和频次；以当前节点结尾的目标路径数等于 prefix-target 的已有频次，回溯时撤销当前前缀。

为什么正确

进入节点前，频次表只包含当前祖先路径的前缀，以及空路径前缀 0。

复杂度分析

时间 O(n)，额外空间 O(h)，递归栈和路径前缀表均随树高增长；h 最坏为 n。Python 深链递归可能触及解释器深度限制，应改用显式栈。

易错点

必须先查询再登记当前前缀，并在回溯时撤销，否则会误计空路径或跨兄弟分支的路径。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def pathSum(self, root, targetSum):
        counts = {0: 1}
        def dfs(node, prefix):
            if not node:
                return 0
            prefix += node.val
            total = counts.get(prefix - targetSum, 0)
            counts[prefix] = counts.get(prefix, 0) + 1
            total += dfs(node.left, prefix)
            total += dfs(node.right, prefix)
            counts[prefix] -= 1
            if counts[prefix] == 0:
                del counts[prefix]
            return total
        return dfs(root, 0)

class Solution {
    private Map<Long, Integer> counts;
    private int targetSum;

    public int pathSum(TreeNode root, int targetSum) {
        this.targetSum = targetSum;
        counts = new HashMap<>(); counts.put(0L, 1);
        return dfs(root, 0);
    }

    private int dfs(TreeNode node, long prefix) {
        if (node == null) {
            return 0;
        }
        prefix += node.val;
        int total = counts.getOrDefault(prefix - targetSum, 0);
        counts.put(prefix, counts.getOrDefault(prefix, 0) + 1);
        total += dfs(node.left, prefix);
        total += dfs(node.right, prefix);
        counts.put(prefix, counts.get(prefix) - 1);
        if (counts.get(prefix) == 0) {
            counts.remove(prefix);
        }
        return total;
    }
}

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<long long, int> counts{{0, 1}};
        function<int(TreeNode*, long long)> dfs = [&](TreeNode* node, long long prefix) {
            if (!node) {
                return 0;
            }
            prefix += node->val;
            auto it = counts.find(prefix - targetSum);
            int total = it == counts.end() ? 0 : it->second;
            counts[prefix]++;
            total += dfs(node->left, prefix);
            total += dfs(node->right, prefix);
            counts[prefix]--;
            if (counts[prefix] == 0) {
                counts.erase(prefix);
            }
            return total;
        };
        return dfs(root, 0);
    }
};

func pathSum(root *TreeNode, targetSum int) int {
	counts := map[int]int{0: 1}
	var dfs func(node *TreeNode, prefix int) int
	dfs = func(node *TreeNode, prefix int) int {
		if node == nil {
			return 0
		}
		prefix += node.Val
		total := counts[prefix-targetSum]
		counts[prefix]++
		total += dfs(node.Left, prefix)
		total += dfs(node.Right, prefix)
		counts[prefix]--
		if counts[prefix] == 0 {
			delete(counts, prefix)
		}
		return total
	}
	return dfs(root, 0)
}

var pathSum = function(root, targetSum) {
    const counts = new Map([[0, 1]]);
    const dfs = (node, prefix) => {
        if (!node) {
            return 0;
        }
        prefix += node.val;
        let total = counts.get(prefix - targetSum) ?? 0;
        counts.set(prefix, (counts.get(prefix) ?? 0) + 1);
        total += dfs(node.left, prefix);
        total += dfs(node.right, prefix);
        counts.set(prefix, counts.get(prefix) - 1);
        if (counts.get(prefix) === 0) {
            counts.delete(prefix);
        }
        return total;
    };
    return dfs(root, 0);
};

function pathSum(root: TreeNode | null, targetSum: number): number {
    const counts = new Map<number, number>([[0, 1]]);
    const dfs = (node: TreeNode | null, prefix: number): number => {
        if (!node) {
            return 0;
        }
        prefix += node.val;
        let total = counts.get(prefix - targetSum) ?? 0;
        counts.set(prefix, (counts.get(prefix) ?? 0) + 1);
        total += dfs(node.left, prefix);
        total += dfs(node.right, prefix);
        counts.set(prefix, counts.get(prefix)! - 1);
        if (counts.get(prefix) === 0) {
            counts.delete(prefix);
        }
        return total;
    };
    return dfs(root, 0);
}

载入编辑器，自己跑一遍 →

其他解法

双重 DFS 枚举起点、逐条累加，最好理解；前缀和把“以当前节点结尾的路径”转化为查哈希表，降到 O(n)。

解法 2：双重深度优先搜索时间 O(n²)，空间 O(h)

外层遍历每个节点，把它当作路径起点。内层从起点向下 DFS，累计路径和，每遇到和等于 targetSum 就计数加 1。所有起点的计数相加就是答案。

思路直接，不需要前缀和技巧。每个节点会被其所有祖先各访问一次，最坏 O(n²)，退化成链时较慢。

class Solution:
    def pathSum(self, root, targetSum):
        def from_node(node, rest):
            # 以 node 为起点、向下延伸且和为 rest 的路径条数
            if not node:
                return 0
            cnt = 1 if node.val == rest else 0
            cnt += from_node(node.left, rest - node.val)
            cnt += from_node(node.right, rest - node.val)
            return cnt

        if not root:
            return 0
        return from_node(root, targetSum) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum)

class Solution {
    private int fromNode(TreeNode node, long rest) {
        if (node == null) return 0;
        int cnt = node.val == rest ? 1 : 0;
        cnt += fromNode(node.left, rest - node.val);
        cnt += fromNode(node.right, rest - node.val);
        return cnt;
    }

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        return fromNode(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
    }
}

class Solution {
public:
    int fromNode(TreeNode* node, long long rest) {
        if (!node) return 0;
        int cnt = node->val == rest ? 1 : 0;
        cnt += fromNode(node->left, rest - node->val);
        cnt += fromNode(node->right, rest - node->val);
        return cnt;
    }

    int pathSum(TreeNode* root, int targetSum) {
        if (!root) return 0;
        return fromNode(root, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
    }
};

func pathSum(root *TreeNode, targetSum int) int {
	var fromNode func(node *TreeNode, rest int) int
	fromNode = func(node *TreeNode, rest int) int {
		if node == nil {
			return 0
		}
		cnt := 0
		if node.Val == rest {
			cnt = 1
		}
		cnt += fromNode(node.Left, rest-node.Val)
		cnt += fromNode(node.Right, rest-node.Val)
		return cnt
	}
	if root == nil {
		return 0
	}
	return fromNode(root, targetSum) + pathSum(root.Left, targetSum) + pathSum(root.Right, targetSum)
}

var pathSum = function(root, targetSum) {
    const fromNode = (node, rest) => {
        if (!node) return 0;
        let cnt = node.val === rest ? 1 : 0;
        cnt += fromNode(node.left, rest - node.val);
        cnt += fromNode(node.right, rest - node.val);
        return cnt;
    };
    if (!root) return 0;
    return fromNode(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
};

function pathSum(root: TreeNode | null, targetSum: number): number {
    const fromNode = (node: TreeNode | null, rest: number): number => {
        if (!node) return 0;
        let cnt = node.val === rest ? 1 : 0;
        cnt += fromNode(node.left, rest - node.val);
        cnt += fromNode(node.right, rest - node.val);
        return cnt;
    };
    if (!root) return 0;
    return fromNode(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
}

二叉树专题的其他题目

查看二叉树全部题目 →