0112. Path Sum ============== 题目信息 -------- :题号: 0112. 路径总和 :难度: Easy :主题: 二叉树、根到叶路径、深度优先搜索、剩余目标 :原题: `LeetCode 0112 `_ :重点: 从保存完整路径压缩为剩余目标,严格限定叶节点成功条件,并利用存在性目标短路搜索 题目重述 -------- 给定二叉树根节点 ``root`` 和整数 ``targetSum``,判断是否存在一条从根开始、在叶节点结束的向下路径,使 路径中所有节点值之和恰好等于 ``targetSum``。 叶节点必须同时没有左孩子和右孩子;内部节点处的前缀和即使等于目标,也不能提前算作成功。空树没有根到叶 路径,返回 ``false``。树中节点总数在 ``0..5000`` 范围内,节点值与 ``targetSum`` 均在 ``-1000..1000`` 范围内,算法不修改树。 自建示例 -------- * 存在目标路径:``root = [6,2,9,1,4,-3,12]``、``targetSum = 12``,返回 ``true``,路径为 ``6 -> 2 -> 4``; * 前缀命中但未到叶:``root = [6,2,null,4]``、``targetSum = 8``,返回 ``false``。``6 -> 2`` 的和 是 ``8``,但节点 ``2`` 还有孩子; * 负数抵消:``root = [2,-3,4]``、``targetSum = -1``,返回 ``true``,不能按剩余值正负剪枝; * 空树:``root = []``,返回 ``false``。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: bool recursiveRemaining(TreeNode* node, int remaining) { if (!node) { return false; } const int nextRemaining = remaining - node->val; if (!node->left && !node->right) { return nextRemaining == 0; } return recursiveRemaining(node->left, nextRemaining) || recursiveRemaining(node->right, nextRemaining); } bool iterativeRemaining(TreeNode* root, int targetSum) { if (!root) { return false; } std::stack> pending; pending.push({root, targetSum}); while (!pending.empty()) { const auto [node, remaining] = pending.top(); pending.pop(); const int nextRemaining = remaining - node->val; if (!node->left && !node->right && nextRemaining == 0) { return true; } if (node->right) { pending.push({node->right, nextRemaining}); } if (node->left) { pending.push({node->left, nextRemaining}); } } return false; } public: bool hasPathSum(TreeNode* root, int targetSum) { return recursiveRemaining(root, targetSum); } }; 题解 ---- 原始路径枚举 ~~~~~~~~~~~~ 答案存在于某一条根到叶路径,最直接的正确方案是深度优先枚举全部路径:进入节点时把值加入当前路径,到叶 节点时求和并与 ``targetSum`` 比较,回到父节点时撤销当前节点。所有合法终点都会被检查,因此不会漏解。 但后续分支并不关心祖先节点分别是什么,只关心它们的和。保存节点数组、在叶节点重新累加、回溯删除路径尾 三项工作都超过了布尔判断所需的信息。沿树向下时,路径和只需一个整数状态。 剩余目标 ~~~~~~~~ 可以携带当前前缀和,也可以把等式移项后维护剩余目标。进入节点前令 ``remaining`` 表示当前路径尚需提供的 总和;选择 ``node`` 后,传给孩子的状态为: .. code-block:: text nextRemaining = remaining - node.value 完整路径命中等价于在叶节点得到 ``nextRemaining == 0``。``recursiveRemaining`` 因而不再保存路径,也不在 每个叶节点重新求和;每个递归分支只复制一个独立的整数。 叶节点边界 ~~~~~~~~~~ 目标相等只能在叶节点判断成功。第二个示例进入节点 ``2`` 后剩余值变成 ``0``,但该节点还有孩子,路径尚未 完成;继续进入 ``4`` 后剩余值变成 ``-4``,最终返回假。 空指针也不是叶节点。递归到空孩子返回 ``false``,避免把只有一个孩子的内部节点通过空分支误判为完整路径。 代码先计算当前节点后的剩余值,再以“左右孩子都空”确认合法终点。 节点值允许为负数,不能根据 ``nextRemaining`` 的正负或是否已经为零剪枝。剩余值为负时,后续负节点仍可能 精确满足目标;剩余值为零时,后续正负值也可能抵消。安全的提前结束只有叶节点命中,或某个分支已经返回真。 状态走读 ~~~~~~~~ 对 ``targetSum = 12`` 的第一个示例,目标路径状态如下: .. list-table:: :header-rows: 1 * - 当前节点 - 进入前 ``remaining`` - 扣除节点后 - 分支含义 * - 6 - 12 - 6 - 还需子路径和为 6 * - 2 - 6 - 4 - 还需子路径和为 4 * - 4 - 4 - 0 - 叶节点精确命中 逻辑或先搜索左子树。左侧一旦找到上述路径,存在性结论已经确定,右子树无需访问;本题只问是否存在,不需要 比较路径优劣,所以短路不会丢失必要答案。 显式栈替代 ~~~~~~~~~~ 递归调用栈实际保存的是尚待处理的 ``(node, remaining)`` 状态。``iterativeRemaining`` 把同一状态放入显式 栈:弹出节点后扣除当前值,再把孩子与新的剩余值一起压入。树没有回边,每个节点只有唯一父路径,因此不需要 访问集合。 代码先压右孩子、再压左孩子,只是让后进先出的栈优先模拟递归的左分支;交换顺序不影响正确性。公开入口采用 递归版,因为它最直接表达“当前路径满足或左、右任一分支满足”的状态定义;显式栈适合避免深递归的场景。 复杂度分析 ~~~~~~~~~~ 最坏访问全部 ``n`` 个节点,时间 ``O(n)``;提前命中时会短路。递归栈或显式 DFS 栈最多保存 ``O(h)`` 个 路径状态,其中 ``h`` 是树高。路径数组已被删除,返回值只占常数空间。按题目范围,路径和在 32 位整数内。