一个简单的问题

Question

 root = removeMin(root);

如果没有把root从新赋值，只是

remove(root);

二叉树在调用是否发生了变化？
我的理解是 root 是一个引用变量，调用 remove 之后应该把二叉树改变了。

Answer 1

liuyubobobo 2019-03-30 13:01:20

我理解你的意思是直接调用removeMin(root);

在大多数情况下，有变化。

但如果你本身要删除的这个最小节点就是根节点，逻辑就发生错误了：）想想看？或者实际跟踪一下？

当然，这是指你只把第一次递归调用改成这个样子。在removeMin里，每一次递归调用，返回值都要被接住的。如果所有的这个递归调用都改成只调用，不反回，那么在所有情况下就都错了。

整体而言，这个运行逻辑，和我在第五章介绍的链表的递归删除，是完全一致的。只不过对于二叉树，要根据值的大小，区别一下左右而已。可以再仔细回顾一下第五章链表的递归删除，尤其是微观解读，理解一下，这个递归删除的结果，为什么一定要返回去：）

继续加油！：）

• 提问者 牡丹丹丹丶 #1

  谢谢老师的解答！