P4065.路径总和Ⅲ

1000ms

Difficulty: 5

所属公司 : Hot100

算法与标签>前缀和

题目描述

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

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

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

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

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

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

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

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

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

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

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

二叉树的节点个数范围是 $[0, 1000]$ 。

$-10^9 <= Node.val <= 10^9$

$-1000 <= targetSum <= 1000$

输入

预期输出（选填）