题解链接

LeetCode 437. 路径总和Ⅲ

题目描述

给定一棵二叉树的根节点 $root$ 和一个整数 $targetSum$。

请你求出该二叉树中节点值之和等于 $targetSum$ 的路径数量。

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

输入描述

第一行输入若干个元素，表示二叉树的层序遍历结果。

相邻两个元素之间用一个空格隔开。

其中，整数表示节点值，$null$ 表示空节点。

第二行输入一个整数 $targetSum$，表示目标路径和。

输出描述

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

样例 $1$

输入

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

输出

3

样例解释

和等于 $8$ 的路径共有 $3$ 条。

样例 $2$

输入

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$