C++二叉树转双向链表时指针传值与传引用的使用疑问

题目要求：给定一棵二叉树（Binary Tree, BT），将其转换为双向链表（Doubly Linked List, DLL）。双向链表节点包含前驱指针、后继指针与数据域，要求链表节点顺序与二叉树的中序遍历顺序完全一致，转换时以原二叉树节点的left指针作为双向链表的前驱（prev）指针，right指针作为双向链表的后继（next）指针，最终返回双向链表的头节点。
示例二叉树结构：

4
   / \
  2   5
 / \
1   3

转换得到的双向链表顺序为：1 <-> 2 <-> 3 <-> 4 <->5

采用指针传值传递root参数时，代码可正常运行，实现如下：

template<typename T>
class BinaryTreeNode 
{
public :
    T data;
    BinaryTreeNode<T> *left;
    BinaryTreeNode<T> *right;

    BinaryTreeNode(T data) {
        this -> data = data;
        left = NULL;
        right = NULL;
    }
};

void inorder(BinaryTreeNode<int>* root,BinaryTreeNode<int>* &prev,BinaryTreeNode<int>* &nroot){
    if(!root) return;
    
    inorder(root->left,prev,nroot);
    if(prev == NULL) nroot=root;
    else{
        root->left = prev;
        prev->right=root;
    }
    prev=root;
    inorder(root->right,prev,nroot);
}

BinaryTreeNode<int>* BTtoDLL(BinaryTreeNode<int>* root) {
    BinaryTreeNode<int>* prev=NULL;
    BinaryTreeNode<int>* nroot=NULL;
    inorder(root,prev,nroot); 
    return nroot;
}

若将inorder函数的root形参修改为指针引用传参，代码如下所示，程序将无法正常工作：

void inorder(BinaryTreeNode<int>*& root,BinaryTreeNode<int>*& prev,BinaryTreeNode<int>* &nroot){
    if(!root) return;
    
    inorder(root->left,prev,nroot);
    if(prev == NULL) nroot=root;
    else{
        root->left = prev;
        prev->right=root;
    }
    prev=root;
    inorder(root->right,prev,nroot);
}

两者本质差异 #

• 指针传值：函数接收的是传入指针的副本，函数内修改这个指针变量本身的指向（给指针变量赋新地址），不会影响调用方的原始指针；但通过指针解引用修改指向内存的内容（比如修改root->left、root->right的值），会真实生效。
• 指针引用传参：形参是调用方原始指针变量的别名，函数内对形参本身做任何赋值修改，都会直接改动调用方的原始指针变量。

传引用版本代码失效原因 #

递归逻辑中，每次向下递归传入的是当前节点的left/right成员指针。当root是引用类型时，递归函数内部的root会直接绑定到父节点的left/right成员上。在后续搭建双向链表、修改当前节点left指针的过程中，会意外改动上层节点的left/right成员值，直接破坏原始树的遍历结构，导致遍历逻辑错乱、指针指向异常，最终运行失败。
而传值版本中，每层递归的root是独立的指针副本，修改副本的指向不会影响父节点存储的left/right地址，仅通过副本访问、修改节点内部的成员指针，逻辑完全符合预期。

选择判断标准 #

• 不需要修改调用方传入的指针变量本身的指向时，一律用指针传值。这是绝大多数场景的正确选择，比如树遍历、链表遍历、仅通过指针读写指向内容的场景。指针传值仅拷贝一个地址长度的数据，开销极低，且不会出现误改外部指针的问题。
• 只有当你明确需要修改调用方所持有的指针变量本身（比如给外部指针动态分配内存、让外部指针指向新的对象地址）时，才使用指针引用传参，这种场景也可以用二级指针实现相同效果。

注意：不要为了所谓的“传引用效率更高”盲目给指针参数加引用，指针本身的长度固定（64位系统下为8字节），拷贝开销可以忽略，乱加引用极易引入难以排查的隐式修改bug。

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