1回答

liuyubobobo

2022-07-26

你的这三个问题基本上是一个问题。归根到底是，你还是没有理解递归的执行过程。

==========

首先，你说的 “将删除的removeMin(node.left)返回的删除的最小值赋值给note.left干什么”这个描述不对。

removeMin(x) 的“宏观语义”是，将以 x 为根节点的二叉树中，删除掉最小值的节点以后，返回结果的二叉树的根节点。

所以，对于 removeMin(node.left)，首先，返回的不是最小值，返回的是一个节点。其次，返回的也不是最小值的节点，而是在以 node.left 为根节点的二叉树中，删掉了最小值的节点以后，得到的结果二叉树的根。

注意，是以 node.left 为根节点的二叉树，删除最小值以后，结果的二叉树的根。（而不是整棵树的根节点）

==========

比如在第一幅图中：

对于节点 41，其 node->left 为 22。以 22 为根的二叉树中，最小值就是这个 22。删掉这个 22 以后，返回的是 33。

那么这个 node->left = removeMin(node->left) 这个赋值作用的意义是什么？恰恰就是你的问题 4 中的“这个链接是怎么做到的”？

在看 41 节点为根的二叉树的时候，因为 41 节点的左孩子不为空，所以执行 41节点->left = removeMin(22 节点)。在以 22 为根节点的二叉树中，删掉了 22，所以返回了 33。 41节点->left= removeMin(22 节点)，removeMin(22 节点) 返回的是 33，所以 41节点->left = 33 节点，做到了将 41 节点的左孩子链接到了 33 节点。

同时，也正是因为有这个赋值操作，所以整个递归函数需要这个 return。

==========

如果上面的解释还让你觉得有点儿晕，我的建议是：

你的整个问题，其实和在链表中删除一模一样，即在这个代码中：https://git.imooc.com/class-105/Play-Algorithms-and-Data-Structures/src/master/08-Recursion/04-LinkedList-and-Recursion/src/Solution5.java

11 行为什么要赋值？

12 行为什么要 return 一个节点？

删除了链表的一个中间节点以后，这个被删除节点前的节点，是怎么和被删除节点后面的节点连接起来的？

我的建议是：再仔细看一遍这一小节关于链表的递归删除过程的微观解读：https://class.imooc.com/lesson/1580#mid=36144

如果认为有必要，这一周的第二章的内容都好好再体会理解一遍：https://class.imooc.com/course/1580

二叉树的递归和链表完全同理，只不过在二叉树中，要根据元素的大小区分一下左右而已。

==========

如果你认为你对于链表的删除，完全理解了的话，而对于这个二叉树中删除最小值的过程还是有点儿晕的话，请你按照我在链表中介绍的方法，用一个小的测试用例，去实际跟踪一下在二叉树中的删除过程到底是怎样的。每一个语句运行后，整个树中到底哪个节点变了，哪个节点的链接变了，到底返回了谁，返回的节点又传给了谁，使得哪个节点连接上了哪个节点，整棵树变成了什么样子。

基本上你能把这样一棵树的过程想明白，我认为就没有什么大问题了。

  41
 /
22
 \
  33
   \
    37

这个问题很重要，完全想明白并不容易，所以花些时间是正常的，也是值得的。想明白这个问题以后，不仅仅意味着你理解了这个代码，也意味着你对递归的理解上升了一个很重要的层次，对于后续课程的学习，乃至对于整个计算机专业的学习，都将非常有帮助。（因为在计算机的底层世界中，递归无处不在。）

继续加油！：）

0