0437. Path Sum III
==================
题目信息
--------
:题号: 0437
:难度: Medium
:主题: 二叉树、向下路径、任意起终点、路径和计数
:原题: `LeetCode 0437 `_
:重点: 路径只能从父节点走向子节点、可从任意节点开始和结束、单节点也算路径、统计路径数量
题目重述
--------
给定二叉树根节点 ``root`` 和整数 ``targetSum``,统计树中节点值之和恰好等于 ``targetSum`` 的路径数量。
每条路径必须沿父节点到子节点的方向连续向下移动,但不要求从根节点开始,也不要求在叶节点结束。不同的起点、终点或经过节点构成不同路径;单个节点本身也可以是一条路径。
树中节点数位于 ``[0, 1000]``,节点值位于 ``[-10^9, 10^9]``,``targetSum`` 位于 ``[-1000, 1000]``。空树返回 0。
自建示例
--------
包含根节点路径和内部路径:
.. code-block:: text
输入:root = [5,3,-2,2,1,null,4],targetSum = 5
输出:2
解释:一条路径是单节点 [5],另一条路径是 3 -> 2。两条路径的起点不同,应分别计数。
空树:
.. code-block:: text
输入:root = null,targetSum = 0
输出:0
解释:不存在节点,因此也不存在任何路径。
前缀和差值对应一条向下路径
----------------------------
沿根到当前节点的路径维护前缀和 ``current``。若某个更早前缀为 ``current - target``,从它之后到当前节点的连续向下路径就恰好和为 ``target``。用哈希表记录当前递归路径上每个前缀和出现次数,访问节点时查询、再加入;离开节点时撤销加入,避免把不同分支拼成一条路径。
初始前缀和 0 出现一次,覆盖从根开始的路径;所有和使用 ``long long``。
C++ 实现
--------
.. code-block:: cpp
class Solution {
int target;
std::unordered_map prefix;
int dfs(TreeNode* node, long long current) {
if (node == nullptr) return 0;
current += node->val;
int result = prefix[current - target];
++prefix[current];
result += dfs(node->left, current);
result += dfs(node->right, current);
if (--prefix[current] == 0) prefix.erase(current);
return result;
}
public:
int pathSum(TreeNode* root, int targetSum) {
target = targetSum;
prefix.clear();
prefix[0] = 1;
return dfs(root, 0);
}
};
代码分析
--------
哈希表只保存当前根到节点的祖先前缀,差值查询一一对应以当前节点结尾的合法路径;回溯删除保证兄弟子树重新使用干净的路径状态。每个节点平均进行常数次哈希操作,时间复杂度为 ``O(n)``,递归和前缀表空间为 ``O(h)`` 到 ``O(n)``。