C++实现基于递归的二叉树路径查找 _ 路径和匹配算法【源码】-C++-PHP中文网

递归查找二叉树路径和需用引用传递vector以避免拷贝开销和状态不同步，回溯时必须push_back后pop_back；仅在叶子节点检查sum==targetsum；空节点须提前判空；路径存在性判断也需完整回溯。

c++实现基于递归的二叉树路径查找 _ 路径和匹配算法【源码】

递归查找二叉树路径是否等于目标和，关键不在“遍历”，而在“回溯时及时剪枝+正确维护路径状态”——否则会得到空路径、重复路径或漏解。

为什么 `std::vector<int>&</int>` 要传引用而不是值？

传值会导致每次递归都拷贝整个路径向量，时间复杂度从 O(n) 退化为 O(n²)，且路径无法回溯更新。更重要的是：子节点 push_back 后，父节点看不到这个改动，导致路径始终为空。

必须用 std::vector<int>& path</int>（左值引用）保证同一份内存被多层递归共享
每次进入子节点前 path.push_back(root->val)，返回前必须 path.pop_back() —— 这是回溯的核心
如果用 const std::vector<int>&</int> 或不加 &，编译可能通过但逻辑必然失败

如何判断当前路径是否满足“和等于 targetSum”？

不能只在叶子节点检查 sum == targetSum 就返回 true，因为路径中途就可能超限；也不能在非叶子节点提前终止，否则会漏掉负数权值的合法路径。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

必须严格在 root->left == nullptr && root->right == nullptr（即叶子节点）时，才检查 sum == targetSum
递归调用前不要做 if (sum > targetSum) return 类似剪枝 —— 二叉树节点值可正可负，targetSum 也可能为负
推荐把当前和作为参数传递：dfs(root, targetSum, 0, path)，避免全局变量或重复计算

遇到空节点或 nullptr 怎么处理？

常见错误是忘记在入口处判空，导致访问 root->val 崩溃；或在递归中对 nullptr 调用 dfs，引发段错误。

入口函数第一行必须写：if (!root) return;
左右子树递归前必须分别判空：if (root->left) dfs(root->left, ...);，不能无条件调用
不要依赖“叶子节点自动终止”——nullptr 不是叶子，它连节点都不是

完整可运行片段（C++11，含路径收集与打印）

void dfs(TreeNode* root, int targetSum, int sum, std::vector<int>& 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(); // 必须回溯！
}
<p>std::vector<:vector>> pathSum(TreeNode* root, int targetSum) {
std::vector<:vector>> result;
std::vector<int> path;
dfs(root, targetSum, 0, path, result);
return result;
}</int></:vector></:vector></p></:vector></int>

最易忽略的一点：即使你只关心“是否存在路径”，也要走完全部回溯逻辑 —— 因为 path.pop_back() 不仅影响后续分支，还决定上层能否继续探索其他子树。跳过它，等于让整棵树的路径状态错乱。