C++ 指针在递归函数中的应用-C++-PHP中文网

递归函数参数常带*而非传值，是因为传值会触发TreeNode完整拷贝，导致left/right指针悬空引发未定义行为；传指针仅传地址（4/8字节），确保所有递归层操作同一节点，支持安全修改与避免崩溃。

c++ 指针在递归函数中的应用

递归函数里传指针不是为了“省空间”，而是为了确保状态可修改、对象不被意外复制、树/图结构不被破坏。

传指针（如 TreeNode*）和传值（如 TreeNode）在递归中效果天差地别：

传值会触发完整拷贝：若 TreeNode 含指针成员（如 left/right），拷贝后新对象的指针仍指向原内存，但原对象生命周期一结束，这些指针立刻悬空；后续访问 node->left->val 就是未定义行为
传指针只传地址（4 或 8 字节），开销恒定，且所有递归层操作的是同一棵树节点
若函数需修改节点内容（比如打标记、改值），必须用指针或引用；传值改的是副本，上层完全无感
标准库容器（如 std::vector）本身不支持直接传值进递归——太大、不可拷贝、或含内部指针，几乎必然用 const std::vector& 或 std::vector*

这是 C++ DFS 递归最常见崩溃点，不是风格问题，是生存问题：

node 是空指针时，node->left 直接解引用 → segmentation fault，程序立即终止，调试器可能连栈帧都抓不到
不能只在首次调用前检查（如 if (root) dfs(root)），因为递归过程中 node->left 或 node->right 完全可能为 nullptr
这个判空必须出现在每个递归入口的第一行，形成“守门员”机制；漏一次，就等于给整个调用链埋雷
若用智能指针（如 std::unique_ptr），检查方式是 if (!node) 或 if (node == nullptr)，语义一致

函数内对指针变量赋值，不影响上层传入的那个指针：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

void dfs(TreeNode* node) { node = nullptr; } → 上层的 root 不变，这行纯属无效操作
但 node->val = 42; 或 node->left = new TreeNode(1); 会真实修改原始树结构，因为 node 指向的是堆上那个实体
回溯场景下（如全排列、N 皇后），常配合指针 + 引用传递状态数组：dfs(int i, vector& path, vector& used)，其中 path 和 used 必须是引用，否则每层都是副本，回退时无法还原
若真要让上层指针被重置（比如释放子树），得传指针的指针：dfs(TreeNode** node)，然后用 *node = nullptr;，但这属于高级控制，日常遍历极少需要

显式栈不是递归的替代品，而是对指针生命周期的主动管理：

stack 存的是地址，pop 出来仍能安全访问 ->left 和 ->right，前提是原始树没被提前析构
stack 每次 push 都调用拷贝构造函数，若 TreeNode 没定义深拷贝逻辑，就会发生浅拷贝：左右指针被原样复制，但所指对象仍是原树节点；一旦原树释放，栈里所有 TreeNode 的 left/right 全部失效
更隐蔽的问题是性能：一个 TreeNode 若含 std::string 成员，拷贝一次就触发字符串内存分配；十万节点遍历，就是十万次 malloc
所以标准写法永远是 stack，并确保树对象的生命周期覆盖整个迭代过程（例如树由 unique_ptr 管理，但迭代期间不 reset）