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方法时，你无法提前知道返回的值是否与第一个参数相同。