0113. Path Sum II ================= 题目信息 -------- :题号: 0113. 路径总和 II :难度: Medium :主题: 二叉树、深度优先搜索、回溯、路径快照 :原题: `LeetCode 0113 `_ :重点: 从逐分支复制完整路径,推导到共享路径缓冲区的追加与撤销,并只在叶节点命中时复制结果 题目重述 -------- 给定二叉树根节点 ``root`` 和整数 ``targetSum``,返回所有节点值之和等于目标的根到叶路径。每条答案用 从根到叶依次经过的节点值数组表示;叶节点必须同时没有左右孩子,内部节点处的前缀命中不能提交。 没有合法路径时返回空数组,多条路径在外层结果中的顺序不限。树中节点总数在 ``0..5000`` 范围内,节点值 与 ``targetSum`` 均在 ``-1000..1000`` 范围内,算法不修改树。 自建示例 -------- * 两条答案:``root = [6,2,9,1,4,-3,12]``、``targetSum = 12``,可返回 ``[[6,2,4],[6,9,-3]]``; * 前缀命中:``root = [3,1,5]``、``targetSum = 3``,返回 ``[]``,根不是叶节点; * 负数路径:``root = [1,-2,-3,1,3,-2,null,-1]``、``targetSum = -1``,合法路径包括 ``[1,-2,1,-1]``; * 空树:``root = []``,返回 ``[]``。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: void collectWithCopies(TreeNode* node, int remaining, std::vector path, std::vector>& result) { if (!node) { return; } path.push_back(node->val); const int nextRemaining = remaining - node->val; if (!node->left && !node->right) { if (nextRemaining == 0) { result.push_back(path); } return; } collectWithCopies(node->left, nextRemaining, path, result); collectWithCopies(node->right, nextRemaining, path, result); } void collectWithBacktracking(TreeNode* node, int remaining, std::vector& path, std::vector>& result) { if (!node) { return; } path.push_back(node->val); const int nextRemaining = remaining - node->val; if (!node->left && !node->right) { if (nextRemaining == 0) { result.push_back(path); } } else { collectWithBacktracking(node->left, nextRemaining, path, result); collectWithBacktracking(node->right, nextRemaining, path, result); } path.pop_back(); } public: std::vector> pathSum(TreeNode* root, int targetSum) { std::vector> result; std::vector path; collectWithBacktracking(root, targetSum, path, result); return result; } }; 题解 ---- 枚举对象 ~~~~~~~~ 每个叶节点唯一对应一条根到叶路径,因此原始搜索空间就是树中的全部叶节点。深度优先搜索沿唯一父链到达每个 叶节点,在那里检查路径和;遍历所有叶节点便不会漏掉任何候选,也不会让同一路径被生成两次。 与只判断“是否存在”不同,本题必须返回每条见证路径。状态不能只保留剩余目标,还要知道从根到当前节点的 完整值序列;找到一条答案后也不能逻辑或短路,因为另一子树中可能还有其他合法路径。 逐分支复制 ~~~~~~~~~~ ``collectWithCopies`` 让 ``path`` 按值传递。每个递归调用获得父路径的独立副本,追加当前值后再进入孩子, 左右分支互不干扰,不需要显式撤销。这是最直接且正确的路径枚举实现。 代价是相同前缀被反复复制。深度为 ``d`` 的节点收到长度约为 ``d`` 的路径副本;即使最终没有答案,这些复制 也已发生。总工作可能达到所有节点深度之和,单侧树最坏为 ``O(n²)``。树结构已经让递归栈保存了当前父链, 没有必要再为每个分支复制同一份前缀。 共享路径回溯 ~~~~~~~~~~~~ ``collectWithBacktracking`` 在全部递归调用之间共享一个 ``path`` 缓冲区,并维护以下不变量:进入某个非空 节点前,``path`` 恰好保存从根到其父节点的值;追加 ``node->val`` 后,它恰好表示根到当前节点的路径。 每个状态按对称步骤工作: #. 进入节点时 ``push_back`` 当前值; #. 扣除当前值,处理叶节点或递归左右孩子; #. 离开节点前 ``pop_back``,恢复父状态的路径。 撤销必须对所有出口执行,包括叶节点未命中时。代码把 ``pop_back`` 放在叶节点分支和递归分支之后,保证任何 非空调用都恰好追加一次、撤销一次;右兄弟开始时不会看到左兄弟遗留的节点值。 结果快照 ~~~~~~~~ 叶节点满足 ``nextRemaining == 0`` 时,``result.push_back(path)`` 必须复制当前路径。共享缓冲区随后还会 弹出和追加;若结果只引用同一个可变对象,回溯会篡改已经记录的答案。复制发生在确实产生输出时,是无法删除 的结果构造成本。 内部节点即使剩余值为零也不能保存。路径必须结束于叶节点,后续孩子仍属于完整路径的一部分。节点值允许为 负数,剩余值变为负数或零都不能作为剪枝条件。 状态走读 ~~~~~~~~ 对第一条答案 ``6 -> 2 -> 4``,共享缓冲区变化如下: .. list-table:: :header-rows: 1 * - 动作 - ``path`` - ``nextRemaining`` - 结果变化 * - 进入 6 - ``[6]`` - 6 - 无 * - 进入 2 - ``[6,2]`` - 4 - 无 * - 进入叶 4 - ``[6,2,4]`` - 0 - 复制 ``[6,2,4]`` * - 离开 4 - ``[6,2]`` - 回到父状态 - 已保存快照不变 * - 离开 2 - ``[6]`` - 回到父状态 - 继续搜索根的右子树 根的右分支随后复用 ``[6]``,生成 ``[6,9,-3]``。两条结果拥有独立向量,外层返回顺序虽由 DFS 决定, 但题目不要求特定顺序。 主解与输出复杂度 ~~~~~~~~~~~~~~~~ 公开入口采用共享缓冲区回溯,因为它只为当前递归路径保存一份可变前缀,并把复制推迟到真实答案产生时。 遍历树本身需要 ``O(n)`` 时间。设所有返回路径长度之和为 ``K``,结果快照必须复制 ``K`` 个值,总时间为 ``O(n + K)``。递归栈与工作路径长度均为 ``O(h)``;返回结果占 ``O(K)`` 空间,不计入工作空间。逐分支复制 法除结果外还可能产生 ``O(nh)`` 级别的累计复制工作。