关于二叉搜索树递归插入函数传递根节点引用的疑问

这个问题问得特别戳中痛点——很多刚接触C++指针和递归的开发者都会在这里绕晕，我来给你掰开揉碎讲清楚：

首先得回忆C++里值传递和引用传递的核心区别：

• 如果函数参数是struct Node* root，这是值传递：函数内部的root是外部传入指针的一个副本，两者指向同一个地址，但本身是完全独立的变量。
• 如果是struct Node* &root，这是指针的引用：函数内部的root就是外部传入的那个指针本身，没有副本，对它的修改会直接作用到原变量上。

接下来看你的插入逻辑：当root是nullptr时，你需要创建一个新节点，并让这个root指向它。如果用值传递会发生什么？

假设你第一次调用RecursiveInsert(nullptr, 5)，函数内部的副本root会被赋值为new Node(5)，但外部的原指针还是nullptr——相当于你在函数里建了个节点，但根本没把它和原来的树连起来，插入操作等于白做。

再看递归过程中的场景：比如你要往某个节点的左子树插入新值，当root->left是nullptr时，调用RecursiveInsert(root->left, key)。如果是值传递，函数里修改的只是root->left的副本，原节点的left指针还是nullptr，新节点依然挂不到树上。

而用指针的引用就不一样了：

• 当你在函数里给root赋值new Node(key)时，修改的就是外部传入的那个指针本身（比如初始的空根指针，或者某个节点的左/右指针）。
• 递归到空位置时，直接把对应的指针（根、左孩子、右孩子）指向新节点，整个树的结构就被正确修改了。

其实还有一种写法是用双重指针（struct Node** root），本质逻辑是一样的——都是为了能在函数内部修改原指针的指向，但引用的写法更简洁易懂，可读性更高。

内容的提问来源于stack exchange，提问作者woHaha