理解递归中的引用参数

Question

我试过从 leetcode 实现排序链表到 BST 的代码 https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/.

我使用递归方法的方法如下。但是这里我们必须在函数参数的头部使用引用（&）。如果我不使用，那么输出将不正确并给出错误的答案。我不明白为什么这里需要引用 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]
如果我在函数参数的 head 中使用 &，BST 的输出应该是这样的：[0,-3,9,-10,null,5]

如果我不在函数参数中使用“&”，那么构建的树将是：

[-10,-10,-3,-10,null,-3] 这是错误的。根节点应为 0。

Answer 1

sortedListUtil 做 两件事：它 returns 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 都会查看输入链表中的相同元素——它的 head 元素。

但是这样，对于每个被 TreeNode *root = new TreeNode(head->val); (3) 放入 ListNode 的元素，head 被推进，以便 下一个 列表中的元素将被放入下一个构造的 ListNode.

因为 head 是函数的参数，它必须通过引用传递 & 所以调用者可以看到变化；否则该变量将是函数调用的局部变量，调用者将看不到更改。

因为我们已经使用了列表的元素，我们必须将指针推进到列表中，这样下一个列表的元素是接下来进入下一个节点的那个。

编辑：给定的sortedListUtil调用在哪里改变head？多少次？就一次！因此，无论在“左”调用中做了什么，head 都是高级的；然后我们取 one 元素（我们所在的那个，在左边被填充之后），相应地前进 head 一个档次，并让“正确的”调用填充右子树！

递归是这样工作的：假设它有效；根据假设得出结论，它适用于较小的情况（此处为左和右）（并且对于最小的情况 - 我们只是 return NULL 并且不触及 head);看到通过 此调用 添加 small 更改不会破坏东西（它不会，我们适当地推进 head 一个档次） ; 然后得出结论，它总体上有效！

理解递归中的引用参数

Understanding reference arguments in recursion

c++

recursion

reference

pass-by-reference

data-structures