第5章｜二叉树与递归
Unit 08 · LeetCode #437 路径总和 III
当前前缀减去目标值，
定位路径开始之前的前缀。
本题不再返回一条最佳路径，而是统计任意起点的向下路径。前缀差把“重新选择起点”压缩成一次哈希查询；回溯则保证频次表只描述当前根到节点的祖先链，不把兄弟分支拼成不存在的路径。
每个节点向父节点返回一个可组合状态，当前节点负责结算答案候选。
递归携带当前前缀和，哈希表保存活动祖先链上各前缀出现次数。
题目要求
给定二叉树根节点 root 和整数 targetSum，返回路径和等于目标值的路径数量。路径不必从根开始，也不必在叶子结束，但必须沿父节点到子节点方向向下。
- 树中节点数为
[0,1000]； - 节点值可为负数，不能使用滑动窗口。
示例与方法
targetSum = 8
输出：3
DFS 维护根到当前节点的前缀和 S。若祖先前缀 S-target 出现过，则对应区间和为目标值。进入节点登记前缀，离开节点撤销。时间 O(n)，活动状态与递归栈 O(h)。
从虚拟起点到当前节点的累计和。
该位置之后到当前节点的路径和恰好为目标。
同一前缀可在活动链上出现多次，每次对应一个不同起点。
离开节点撤销当前前缀，使哈希表始终只代表一条祖先链。
每个旧前缀 needed 对应一条以当前节点结尾的目标路径。
进入登记，离开撤销，兄弟分支之间不能共享局部前缀。
当前祖先链上的前缀
prefix_count 频次表
调用栈
频次表不变量
prefix_count 只包含虚拟前缀到当前节点父亲之间的活动前缀。
操作顺序
查询旧前缀 → 登记当前前缀 → 递归左右 → 撤销当前前缀。
左子树中的前缀不再是右子树节点的祖先前缀。若离开左分支后仍保留它，哈希查询可能把“先向上再向下”的两段拼成题目不允许的路径。
当前节点 11 的 current_sum=18，需要旧前缀10。此时频次表中 10 出现一次，而左分支前缀已经撤销。
避免 target=0 时让当前前缀与自己配对，虚构长度为0的路径。
让频次表恢复到进入当前节点前的祖先链状态。
同一旧前缀出现多次时，会丢失多个合法起点。
兄弟分支前缀会相互污染，形成非向下路径。
迁移目标：LeetCode #560 和为 K 的子数组
前缀差和频次统计完全复用。数组只有一条从左到右的历史链，不存在递归返回兄弟分支，因此不需要回溯撤销。
LeetCode #560｜和为 K 的子数组
迁移原题
给定整数数组 nums 和整数 k，返回数组中和为 k 的连续子数组数量。
示例与变化
输出：2
输出：2
仍然先查询 current_sum-k，再登记当前前缀；但历史前缀永远属于同一条扫描链，无需撤销。
保留前缀差公式与频次含义
旧前缀必须位于当前祖先链，递归离开节点后撤销。
所有旧前缀都位于当前索引之前，始终是合法历史。
数组扫描到当前前缀 S 时，应增加多少个答案？
为什么数组不需要撤销前缀？
索引只向右移动，所有已登记前缀都位于当前索引之前。
返回父节点后，刚离开的分支不再属于下一分支的祖先链。
数组循环处理完一个元素后，应执行什么？
把递归状态压缩为一次线性循环
真实轨迹：nums = [1,1,1]，k = 2
页面不会自动跳转。请先观察当前状态，再决定是否继续。