删除二叉搜索树中的节点

  • 遇到这样一道题目，蒙住了，这一行代码为什么不可以删除temp节点呀
  • 逻辑是找到root右子树最左侧节点，然后把值改了，然后删除掉这个temp

img

从二叉树删除某个节点，不是将应该删除的这个节点设置为null，而是将该节点释放，并且修改它的父节点，将父节点的lfeft或者right指向新的节点。以题目图中为例，当找到节点3为待删除节点时，将节点3的两个子节点找出较大的那个（对于右子树，是找到较小的那个），也就是节点4，上提一层，2成为4的左子节点；3的父节点是5，它是5的左节点，将5的左节点设置为4，原3节点释放。
另外，原图中22-29这些行，可以不用这样判断，因为涉及两个子节点都不为空的情况，参考上面描述。