当前位置：

首页 > 编程开发 > C++实现基于递归的二叉树路径查找 _ 路径和匹配算法【源码】

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

作者：EasyWind 时间：2026-05-02 浏览：0

递归查找二叉树路径和需用引用传递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>& 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()，不仅影响着当前分支的后续探索，更决定了上层递归能否正确地去搜索其他子树。跳过它，整个树的路径状态就会陷入混乱。

本文内容来源于互联网，如有侵权请联系删除。

作者最新文章

淘宝闪购“等灯不计时”机制解析：政策、技术与多方协同 2026-09-08 18:00

一加自研电竞三芯P4/G3/T3确认：一加16首发，支持185FPS及9000mAh电池 2026-09-08 16:52

抖音拍摄剪辑教程：从竖屏运镜到卡点成片 2026-09-03 06:05

Excel筛选大于指定数值：操作步骤与结果验证 2026-09-03 06:03

PDF添加文字水印：位置、透明度与字号设置指南 2026-09-03 06:01

编程开发 C++

上一篇： Python使用正则表达式将多个空格替换为一个空格

下一篇： Photoshop快捷键修改在哪里？PS2020快捷键设置方法

相关文章更多

C++动态数组初始化怎么写？常用语句与代码示例

内存管理 C++ 动态数组

09.21

C++类构造与析构函数详解

C++

08.17

C++中std::upper

C++

08.16

C++常对象与成员解析

C++

08.15

using namespace 使用中遇到的问题怎么解决

08.07

c语言函数递归实操经验总结：这些技巧很实用

08.07

c语言函数递归怎么选？常见方案对比分析

08.07

Objective-C 内存管理入门：从 alloc 到 dealloc 的生命周期详解

08.07

如何正确使用 dealloc 以避免 iOS 应用中的内存泄漏

08.07

深入理解 Objective-C 中的 dealloc 方法：内存管理核心机制

08.07

热门文章更多

Yandex中文入口及登录使用全攻略 51漫画高清入口及最新章节更新 B站免费入口永久有效网址推荐 58动漫网入口及永久访问方法蓝海书屋免费小说全本阅读推荐入口 B站免费入口网站高效连接方法高德地图开启海拔显示方法 ACG动漫资源站官网入口及全集链接

精品专题更多

装机必备

正软商城装机必备专区，精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件，帮助用户快速完成新电脑软件配置。

Windows

正软商城Windows软件专区，汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件，提供软件介绍、系统要求、正版授权及购买下载服务。

macOS软件

正软商城macOS软件专区，精选适用于Mac电脑的办公、设计、影音、效率、开发和系统工具，提供软件功能介绍、macOS兼容版本、正版授权及购买下载服务。

IOS软件

正软商城iOS软件专区，精选适用于iPhone和iPad的办公、学习、影音、设计、效率及AI应用，提供功能介绍、适用设备、系统要求和正版获取方式等信息。

正软商城AI软件专区，汇集AI写作、AI绘画、AI视频、AI办公、AI编程、AI翻译、智能客服和数据分析等人工智能工具，提供功能介绍、适用平台、收费方式及正版购买信息。

PDF教程

PDF教程适合刚接触PDF文件的用户,本文整理PDF打开、编辑、转换、合并、压缩等常见基础操作。通过这些教程可以快速了解PDF文件怎么处理,解决办公、学习和资料科整理中的常见问题。使用极轻PDF可在线完成多种PDF操作，适合新手快速上手。

Mac软件更多

灵活计算器

灵活计算器是一款笔记式算数应用，支持实时计算、动态关联和云端同步功能。记录、整理和输出之间的过渡会更自然，适合长期写作、做笔记或持续沉淀个人内容。

macOS软件 Android IOS软件装机必备

赤友清理大师

赤友清理大师是一款为 Mac 设计的智能清理优化工具，可精准扫描垃圾、大文件、重复文件等，释放磁盘空间。做扫描整理、文字提取和表格转换时，它能把识别后的处理步骤接得更顺，资料录入这类场景会省下不少时间。

macOS软件装机必备

极度公式

极度公式是一款跨平台专业LaTeX公式识别编辑软件，支持OCR公式识别和多平台编辑。和使用说明，避免使用，享受完整功能与稳定支持。做扫描整理、文字提取和表格转换时，它能把识别后的处理步骤接得更顺，资料录入这类场景会省下不少时间。

Windows macOS软件 Linux 装机必备

图几

图几是一款适用于 macOS 的截图、标注与美化工具，支持离线操作保障隐私。界面整理和高频系统操作被放到一起考虑，桌面或窗口内容一多时，管理起来会更省心。

macOS软件装机必备

密码键盘

密码键盘是一款兼具安全性与便捷性的高效密码管理器。日常使用里的持续防护和信息管理会更突出，适合把安全控制放进长期使用流程中的场景。

Windows macOS软件 Android IOS软件装机必备

思源笔记

思源笔记是一款本地笔记软件，提供所见即所得的编辑方式，为长文写作带来顺滑的体验。记录、整理和输出之间的过渡会更自然，适合长期写作、做笔记或持续沉淀个人内容。

Windows macOS软件 Android IOS软件装机必备

Office 365 简体中文

一款文字处理软件，一种订阅式的跨平台办公软件，基于云平台提供多种服务，通过将 Excel 和 Outlook 等应用与 OneDrive 和 Microsoft Teams 等强大的云服务相结合，Office 365 可让任何人使用任何设备随时随地创建和共享内容。

WALTR PRO

WALTR是一款电脑至iOS文件传输转换工具，操作简单，快速实现文件识别与传送。做扫描整理、文字提取和表格转换时，它能把识别后的处理步骤接得更顺，资料录入这类场景会省下不少时间。

Windows macOS软件

CodeExpander

CodeExpander 是一款快捷短语输入增强工具，通过键入缩写自动展开为自定义文段，提升工作效率。任务管理和过程控制会更完整，持续下载、批量同步或需要稳定传输流程的场景会更适合它。

Windows macOS软件

Mountain Duck

Mountain Duck 是一款能将多个网盘挂载到本地的工具，像本地磁盘一样使用网盘。清理链路的完整性会更好一些，做应用卸载、残留处理和空间整理时，通常能少走很多手动排查步骤。

Windows macOS软件

Menuist

Menuist 是一款面向 macOS 的 Finder 右键菜单增强工具，主要用来补充新建文件、快捷导航等常用操作，让日常文件管理和访问路径时更高效、更顺手。

macOS软件

Mole

Mole 是一款专为 Mac 设计的深度清理优化工具，涵盖缓存清理、应用管理及实时状态监控等功能。清理链路的完整性会更好一些，做应用卸载、残留处理和空间整理时，通常能少走很多手动排查步骤。

macOS软件

WINDOWS 更多

Windows 10

Windows 10 是一款微软推出的经典操作系统，拥有硬件兼容性与多任务处理能力。它更偏向把系统状态查看和常用调节动作放在一起，适合需要持续观察和微调设备状态的场景。

Windows 10 Windows 操作系统装机必备

极度公式

Windows macOS软件 Linux 装机必备

密码键盘

密码键盘是一款兼具安全性与便捷性的高效密码管理器。日常使用里的持续防护和信息管理会更突出，适合把安全控制放进长期使用流程中的场景。

Windows macOS软件 Android IOS软件装机必备

思源笔记

Windows macOS软件 Android IOS软件装机必备

傲梅轻松备份

傲梅轻松备份是一款专业易用的数据备份软件，为重要数据提供安全保障。日常使用里的持续防护和信息管理会更突出，适合把安全控制放进长期使用流程中的场景。

Windows 装机必备

Office 365 简体中文

Wise Folder Hider Pro

Wise Folder Hider Pro 是一款专业级文件和文件夹隐藏加密软件，为私密数据添加多重保护。高频操作更强调就近处理，浏览、整理和跨目录移动文件时，来回切换和重复点击都会少很多。

Windows

WALTR PRO

Windows macOS软件

CodeExpander

Windows macOS软件

PinStack

PinStack是一款轻量级的Windows平台剪贴板管理工具，优化您的剪贴板使用体验。它更偏向把系统状态查看和常用调节动作放在一起，适合需要持续观察和微调设备状态的场景。

Windows

Mountain Duck

Windows macOS软件

Seer

Seer是一款在Win平台下的空格键功能增强效率工具，只需轻敲空格键，就能预览几乎任何格式的文件。它更适合把零散的小功能集中起来使用，处理高频琐碎任务时会更省事。

Windows

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

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

为什么 std::vector 要传引用而不是值？

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

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

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

为什么 `std::vector` 要传引用而不是值？