路径总和 III

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

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

约定

• 树中节点数目范围在 [0, 1000]
• -10^9 <= Node.val <= 10^9
• -1000 <= targetSum <= 1000
• 输入树以力扣层序数组形式给出，null 表示空节点。

输入

• root：二叉树根节点（TreeNode）
• targetSum：目标和

输出

和为 targetSum 的向下路径总数。

示例一

输入：

root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], targetSum = 8

输出：

3

解释：存在 3 条路径和为 8：5 -> 3、5 -> 2 -> 1、-3 -> 11。

示例二

输入：

root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1], targetSum = 22

输出：

3

复杂度要求

• 时间复杂度：O(n)，每个节点访问一次
• 空间复杂度：O(h)，哈希表与递归栈深度