0112. Path Sum¶
题目信息¶
- 题号:
路径总和
- 难度:
Easy
- 主题:
二叉树、根到叶路径、深度优先搜索、剩余目标
- 原题:
- 重点:
从保存完整路径压缩为剩余目标,严格限定叶节点成功条件,并利用存在性目标短路搜索
题目重述¶
给定二叉树根节点 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++ 实现¶
#include <stack>
#include <utility>
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<std::pair<TreeNode*, int>> 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 后,传给孩子的状态为:
nextRemaining = remaining - node.value
完整路径命中等价于在叶节点得到 nextRemaining == 0。recursiveRemaining 因而不再保存路径,也不在
每个叶节点重新求和;每个递归分支只复制一个独立的整数。
叶节点边界¶
目标相等只能在叶节点判断成功。第二个示例进入节点 2 后剩余值变成 0,但该节点还有孩子,路径尚未
完成;继续进入 4 后剩余值变成 -4,最终返回假。
空指针也不是叶节点。递归到空孩子返回 false,避免把只有一个孩子的内部节点通过空分支误判为完整路径。
代码先计算当前节点后的剩余值,再以“左右孩子都空”确认合法终点。
节点值允许为负数,不能根据 nextRemaining 的正负或是否已经为零剪枝。剩余值为负时,后续负节点仍可能
精确满足目标;剩余值为零时,后续正负值也可能抵消。安全的提前结束只有叶节点命中,或某个分支已经返回真。
状态走读¶
对 targetSum = 12 的第一个示例,目标路径状态如下:
当前节点 |
进入前 |
扣除节点后 |
分支含义 |
|---|---|---|---|
6 |
12 |
6 |
还需子路径和为 6 |
2 |
6 |
4 |
还需子路径和为 4 |
4 |
4 |
0 |
叶节点精确命中 |
逻辑或先搜索左子树。左侧一旦找到上述路径,存在性结论已经确定,右子树无需访问;本题只问是否存在,不需要 比较路径优劣,所以短路不会丢失必要答案。
显式栈替代¶
递归调用栈实际保存的是尚待处理的 (node, remaining) 状态。iterativeRemaining 把同一状态放入显式
栈:弹出节点后扣除当前值,再把孩子与新的剩余值一起压入。树没有回边,每个节点只有唯一父路径,因此不需要
访问集合。
代码先压右孩子、再压左孩子,只是让后进先出的栈优先模拟递归的左分支;交换顺序不影响正确性。公开入口采用 递归版,因为它最直接表达“当前路径满足或左、右任一分支满足”的状态定义;显式栈适合避免深递归的场景。
复杂度分析¶
最坏访问全部 n 个节点,时间 O(n);提前命中时会短路。递归栈或显式 DFS 栈最多保存 O(h) 个
路径状态,其中 h 是树高。路径数组已被删除,返回值只占常数空间。按题目范围,路径和在 32 位整数内。