删除任意节点，如果要删除节点左右子树为空，疑问
来源：6-12 删除二分搜索树的任意元素
微暖丶温情
2019-04-18
假如我们删除42的节点，42的节点左子树，右子树都是空
那么它肯定走第一张图中的方法，返回的是node.right
可是node.right不是null吗，那么返回的就是null？
之前返回的不都是当前要删除的节点吗？
如果返回的是当前要删除的节点，那么会什么root 等于这个要删除的节点？
写回答
1回答
-
这个函数的语义返回的不是待删除的节点，而是返回删除节点后，新的二分搜索树的根节点。
所以，要删除42，返回的空，是指，以42为根节点的二分搜索树，删除42以后，剩下的是一棵空树。
这棵空树，传给了他的父亲节点，也就是50的左子树，完成了删除动作：
之后50这个节点是把自己返回回去，而不是这个空。也就是50-42-53这棵以50为根的二分搜索树，删除掉42以后，新的二分搜索树的根节点，还是50，返回了回去。
整个过程以此类推。
其实，这个过程，和我们前面讲的链表的递归删除，是非常像的，可以在参考这个问答：https://coding.imooc.com/learn/questiondetail/70176.html，结合前面讲解的链表的递归删除过程，尤其是微观语义，理解一下整个程序是如何执行的：）
加油！：）
112019-04-18
相似问题