c++ - 理解递归中的引用参数

Question

我已经尝试从 leetcode 实现 Sorted Linked List to BST 的代码
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/ .
我曾经使用递归方法的方法如下。但是这里我们必须在函数参数的 head 中使用引用 (&)。如果我不使用，那么输出将不正确并给出错误答案。我无法理解为什么这里需要引用 head 或者在什么类型的递归场景中我们应该这样做。我有时会在递归中感到困惑。

int countNodes(ListNode* head) {
    int count = 0;
    ListNode *temp = head;
    
    while (temp != NULL) {
        temp = temp->next;
        count++;
    }
    return count;
}

TreeNode *sortedListUtil(ListNode *&head, int n) { 
    // head should be ref, if we dont use & , 
    //   unexpected output will come
    if (n <= 0)
        return NULL;
    
    TreeNode *left = sortedListUtil(head, n/2);
    
    TreeNode *root = new TreeNode(head->val);
    
    root->left = left;
    head = head->next;
    
    root->right = sortedListUtil(head, n - n/2 -1); 
        // recur for remaining nodes
    
    return root;
}

TreeNode* sortedListToBST(ListNode* head) {
    if (head == NULL)
        return NULL;
    
    int n = countNodes(head);
    return sortedListUtil(head, n);
}

输入链表是: head = [-10,-3,0,5,9]如果我在函数参数中使用 & in head ，BST 的输出应该是这样的: [0,-3,9,-10,null,5]如果我不在函数参数中使用“&”，那么构造的树将是:
[-10,-10,-3,-10,null,-3] 这是错误的。根节点应为 0。

Answer 1

sortedListUtil做两件事:它返回 root (1)，它也改变了head (2) 以便它的调用从调用到另一个递归调用沿着列表前进:

TreeNode *sortedListUtil(ListNode *&head, int n) { 
    // head should be ref, if we dont use & , 
    //   unexpected output will come
    if (n <= 0)
        return NULL;
    
    TreeNode *left = sortedListUtil(head, n/2);
    
    TreeNode *root = new TreeNode(head->val);  // <<<<------ NB (3)
    
    root->left = left;
    head = head->next;  // <<<<--------------------- NB (2)
    
    root->right = sortedListUtil(head, n - n/2 -1); 
        // recur for remaining nodes
    
    return root;        // <<<<--------------------- NB (1)
}

不改变 head , 每次调用 sortedListUtil将查看输入链表中的相同元素——它的头元素。
但是这样，对于放入 ListNode 的每个元素来自 TreeNode *root = new TreeNode(head->val); (3)、 head被提前，以便列表中的下一个元素将被放入下一个构造的 ListNode 中。 .
自 head是函数的参数，必须通过引用传递 &所以调用者可以看到变化；否则变量将是函数调用的局部变量，调用者将看不到更改。
由于我们已经使用了列表的元素，我们必须将指针推进到列表中，以便下一个列表的元素是下一个进入下一个节点的元素。

编辑:给定的 sortedListUtil 在哪里调用更改 head ?多少次？就一次!所以无论在“左”调用中做了什么， head先进；然后我们取一个元素(我们所在的那个，在左边被填满之后)，前进 head相应地一个档次，让“正确”的调用填充正确的子树!
递归是这样工作的:假设它有效；通过假设得出结论它适用于较小的情况(这里，左和右)(以及最小的情况 - 我们只返回 NULL 并且不接触 head )；看到通过此调用添加小的更改不会破坏事物(它不会，我们适本地将 head 提高一个档次)； 然后 总结它总体上有效!