Leetcode450:删除二叉搜索树中的节点
题目
https://leetcode-cn.com/problems/delete-node-in-a-bst/
这道题完全可以当作一个知识点来对待。
题解
思路
众所周知，一颗二叉搜索树的中序遍历是一个递增序列，这是二叉搜索树最基本的性质之一。
某个节点node的后继节点successor，就是中序遍历中仅次于node的后一个节点，是比node大的节点当中最小的节点。node的右子树中最左边那个节点就是successor。
某个节点node的前继节点predecessor，就是中序遍历中稍大于node的前一个节点，是比node小的节点当中最大的节点。node的左子树中最右边那个节点就是successor。
我们要维护这个性质，所以，当删除一个节点时，我们要拿这个节点的后继节点successor或者前继节点predecessor来替换它，然后递归的删除它的后继节点或者前继节点。比如删除[1,2,3,4,5]中的3，我们就拿4来替换它（或者拿2替换）。然后为了删除4，拿5来替换。5后面没有节点了，就直接删除5。
删除的时候可能有三种情况：
- 要删除节点是叶节点。直接删除就好了。
- 要删除的节点只有左子树，或者只有右子树。如果是左子树，就找前继节点替换；如果是右子树，就找后继节点替换。
- 要删除的节点既有左子树又有右子树。前继，后继都可以。一般我们选择后继。
上面的描述比较易于理解，但为了写代码方便，我们稍作改变：
- 要删除节点是叶节点。直接删除。
- 要删除的节点有右子树，就拿后继替换。
- 否则，拿左继替换。
代码
先看下ac的代码吧：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def get_successor(self, node):
node = node.right
while node.left:
node = node.left
return node.val
def get_predecessor(self, node):
node = node.left
while node.right:
node = node.right
return node.val
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root:
return None
if key > root.val:
root.right = self.deleteNode(root.right, key)
elif key < root.val:
root.left = self.deleteNode(root.left, key)
else:
if (not root.left) and (not root.right):
root = None
elif root.right:
root.val = self.get_successor(root)
root.right = self.deleteNode(root.right, root.val) # 从root.right开始删除，
# 如果从当前root删除，会死循环
else:
root.val = self.get_predecessor(root)
root.left = self.deleteNode(root.left, root.val)
return root
为什么非要优先找后继节点呢？其实你优先找前继节点也可以，把这段代码改成这样：
elif root.left:
root.val = self.get_predecessor(root)
root.left = self.deleteNode(root.left, root.val)
else:
root.val = self.get_successor(root)
root.right = self.deleteNode(root.right, root.val)
为什么非要写成root.left = xxx，root.right = xxx呢？
我把root.right = self.deleteNode(root.right, key)改成self.deleteNode(root.right, key)；
以及后面三处的赋值语句都改成了直接递归，结果只和正确答案差了一点，就是在递归的末端的叶子节点当中root=None没有生效。也就是说叶子节点没有成功删除。
我猜想可能是因为python的引用传递有关，这条赋值语句修改的只是形参而不是实参，所以无效！
总之递归的代码好难写qwq，孩子根本想不到…