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

递归查找二叉树路径和需用引用传递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>& 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> pathSum(TreeNode* root, int targetSum) {
    std::vector> result;
    std::vector path;
    dfs(root, targetSum, 0, path, result);
    return result;
}

最后提醒一个最容易被忽略的点：即便你只关心“路径是否存在”，也必须走完全部的回溯逻辑。因为那个看似不起眼的 path.pop_back()，不仅影响着当前分支的后续探索，更决定了上层递归能否正确地去搜索其他子树。跳过它，整个树的路径状态就会陷入混乱。