路径总和Ⅲ（前缀和法）

题解思路

这道题目要求我们计算二叉树中所有路径和等于给定目标值 targetSum 的路径数量。可以利用 前缀和 的思路来优化算法。

关键点分析

1. 路径的定义：路径不一定从根节点开始，也不一定在叶子节点结束，路径必须是从父节点到子节点进行传递。
2. 前缀和的思路：前缀和是一种在数组或树中计算区间和的技巧，可以通过记录路径的前缀和来减少冗余计算，避免重复遍历子树。

Leetcode 48.路径总和Ⅲ-原题链接

题目内容

给定一个二叉树的根节点 $root$，和一个整数 $targetSum$，求该二叉树里节点值之和等于 $targetSum$ 的 路径的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）

输入描述

第一行是一个整数 $n(0 <= n <= 1000)$，表示二叉树中的节点总数。

第二行为一个长度为 $n$ 的二叉树的序列化数组，节点值之间用空格隔开，空节点用null表示。

第三行是一个整数 $targetSum$。

输出描述

输出一个整数，表示路径和等于 $targetSum$ 的路径数量。

样例1

输入

11
10 5 -3 3 2 null 11 3 -2 null 1
8

输出

3

说明

和等于$8$ 的路径有 $3$ 条，如图所示

样例2

输入

13
5 4 8 11 null 13 4 7 2 null null 5 1
22

输出

3

提示

• 二叉树的节点个数的范围是$[0,1000]$
• $-10^9 <= Node.val <= 10^9$
• $-1000 <= targetSum <= 1000$