java - 递归:传递给函数的变量是否需要跟踪和更新？

Question

我正在查看从二叉搜索树中删除节点的代码，我有点困惑

Node deleteRec(Node root, int key)
    {
        /* Base Case: If the tree is empty */
        if (root == null)  return root;

        /* Otherwise, recur down the tree */
        if (key < root.key)
            root.left = deleteRec(root.left, key);
        else if (key > root.key)
            root.right = deleteRec(root.right, key);

        // if key is same as root's key, then This is the node
        // to be deleted
        else
        {
            // node with only one child or no child
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;

            // node with two children: Get the inorder successor (smallest
            // in the right subtree)
            root.key = minValue(root.right);

            // Delete the inorder successor
            root.right = deleteRec(root.right, root.key);
        }

        return root;
    }

为什么我们需要将函数调用的结果存储在多个地方的root.left 和root.right 变量中？由于 root 的值，即引用被传递给函数，后续调用中的任何更改都会自动更新树，不是吗？那么为什么要将值存储在变量中呢？为了阐明我的观点，下面是另一段代码

// A recursive function used by topologicalSort
void topologicalSortUtil(int v, boolean visited[],
                         Stack stack)
{
    // Mark the current node as visited.
    visited[v] = true;
    Integer i;

    // Recur for all the vertices adjacent to this
    // vertex
    Iterator<Integer> it = adj[v].iterator();
    while (it.hasNext())
    {
        i = it.next();
        if (!visited[i])
            topologicalSortUtil(i, visited, stack);
    }

    // Push current vertex to stack which stores result
    stack.push(new Integer(v));
}

这里堆栈被传递给函数，我们只是在进一步的函数调用中一次又一次地使用它，因为我们知道堆栈将在调用之间不断更新。

我是不是遗漏了什么或者我理解错了什么？有人可以帮我理解吗。谢谢!!

Answer 1

当你删除树的一个节点时，父节点的左指针或右指针可能需要更新。最简单的情况是被删除的 not 是叶子:在这种情况下，指向它的链接必须设置为 null。

另外，如果被删除的节点恰好是根节点，则必须更新指向根的指针。

当您调用 deleteRec 方法时，您无法提前知道返回的值是否与第一个参数相同。