C++递归实现二叉树路径查找与路径和匹配算法源码
作者:技术拾光时间:2026-05-28 18:36:01浏览:598
递归查找二叉树路径和需用引用传递vector以避免拷贝开销和状态不同步,回溯时必须push_back后pop_back;仅在叶子节点检查sum==targetSum;空节点须提前判空;路径存在性判断也需完整回溯。 递归查找二叉树路径是否等于目标和,关键不在“遍历”,而在“回溯时及时剪枝+正确维护路径
递归查找二叉树路径和需用引用传递vector以避免拷贝开销和状态不同步,回溯时必须push_back后pop_back;仅在叶子节点检查sum==targetSum;空节点须提前判空;路径存在性判断也需完整回溯。

递归查找二叉树路径是否等于目标和,关键不在“遍历”,而在“回溯时及时剪枝+正确维护路径状态”——否则会得到空路径、重复路径或漏解。
为什么 std::vector 要传引用而不是值?
这里有个常见的“坑”:如果选择传值,每次递归调用都会拷贝整个路径向量。这么一来,时间复杂度会从理想的 O(n) 退化到 O(n),性能开销巨大。更关键的是逻辑错误——子节点对路径的修改(比如 push_back),父节点根本感知不到,导致最终路径始终为空。
- 正确的做法是使用
std::vector(左值引用),确保所有递归层操作的是同一块内存。& path - 记住一个固定动作:进入子节点前
path.push_back(root->val),返回前必须执行path.pop_back()。这就是回溯的核心机制。 - 如果误用了
const引用或者省略了&,代码可能照样编译,但运行逻辑必然出错。
如何判断当前路径是否满足“和等于 targetSum”?
判断时机和条件需要格外小心。既不能在叶子节点才检查,也不能在非叶子节点提前终止,否则都会出问题。
- 必须严格限定在
root->left == nullptr && root->right == nullptr(即到达叶子节点)时,才进行sum == targetSum的判断。 - 切记不要在递归调用前做类似
if (sum > targetSum) return的剪枝。因为二叉树节点值可正可负,目标值targetSum也可能为负数,中途的“超限”并不代表后续没有合法路径。 - 一个推荐的做法是:将当前路径和作为参数传递,例如
dfs(root, targetSum, 0, path)。这能避免使用全局变量,也减少了重复计算。
遇到空节点或 nullptr 怎么处理?
空指针处理是崩溃的高发区。常见的失误包括:忘记在函数入口判空,导致访问 root->val 时程序崩溃;或者在递归中无条件对 nullptr 调用 dfs,引发段错误。
立即学习“C++免费学习笔记(深入)”;
- 入口函数的第一行,务必加上:
if (!root) return; - 在递归左右子树前,必须分别判空:
if (root->left) dfs(root->left, ...);,不能想当然地直接调用。 - 别指望“叶子节点自动终止”——
nullptr根本不是节点,对它进行操作是未定义行为。
完整可运行片段(C++11,含路径收集与打印)
void dfs(TreeNode* root, int targetSum, int sum, std::vector& path, std::vector<:vector>>& result) { if (!root) return; path.push_back(root->val); sum += root->val; if (!root->left && !root->right && sum == targetSum) { result.push_back(path); } if (root->left) dfs(root->left, targetSum, sum, path, result); if (root->right) dfs(root->right, targetSum, sum, path, result); path.pop_back(); // 必须回溯! } std::vector<:vector>> pathSum(TreeNode* root, int targetSum) { std::vector<:vector>> result; std::vector path; dfs(root, targetSum, 0, path, result); return result; }
最后提醒一个最容易被忽略的点:即便你只关心“路径是否存在”,也必须走完全部的回溯逻辑。因为那个看似不起眼的 path.pop_back(),不仅影响着当前分支的后续探索,更决定了上层递归能否正确地去搜索其他子树。跳过它,整个树的路径状态就会陷入混乱。
