代码随想录算法训练营第二十二天（二叉树篇）|450. 删除二叉搜索树中的节点

周一参加了公务员的省考，虽然只是抱着学习的心态尝试的，并不想上岸，但还是被打击到了，自己果然暂时还是“干啥啥不行”的状态，当然也是因为自己哪方面都不够非常努力。那么，继续努力吧，趁身体和大脑还能拼搏的时候。

450. 删除二叉搜索树中的节点

学习材料：代码随想录 (programmercarl.com)

题目链接：450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

解题思路

这道题一开始让我不确定的是对二叉树来说，删除节点到底意为着什么。感觉和链表的想法有些类似。对链表来说，删除当前节点，意味着让此节点的前一个节点指向此节点的后一个节点。那么同理，如果对于二叉树，假如一个节点只有左/右子树，没有右/左子树，那么删除它意味着让它的父节点直接指向它的左/右子树，把它跳过。那么这个思路如何通过递归体现？这相当于我们将此节点的左/右子树直接向上一层返回，上一层为此节点父节点的子树。也就是说，我们直接把父节点的子树由当前（要被删除的）节点改为当前节点的左/右子树，跳过当前节点。

理解了删除二叉树节点的基本思路，便可进一步考虑下面四种情况：

1. 是叶子节点，则直接返回空。
2. 左子树不为空，右子树为空：向上返回当前节点的左子树。
3. 左子树为空，右子树不为空：向上返回当前节点的右子树。
4. 左右子树都不为空：将节点的左子树“移花接木”到当前节点的右子树中值最小的节点（即左下方）的左节点。此时可视为上面第三种情况（左子树已经接好了，就可以忽略为空），直接返回右子树。

代码实现

    def deleteNode(self, root, key):
        if root == None:
            return None
        if root.val == key:
            if not root.left and not root.right:
                return None
            elif root.left and not root.right:
                return root.left
            elif not root.left and root.right:
                return root.right
            elif root.left and root.right:             
                cur = root.right
                while cur.left:
                    cur = cur.left  # 找到当前节点右子树的最左下方的节点
                cur.left = root.left
                return root.right
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        return root

注意处理好root等于key的核心条件后，不要忘记寻找二叉树（要被删除的）节点的总框架，即不要漏掉下面这段代码：

elif root.val < key:
    root.right = self.deleteNode(root.right, key)
elif root.val > key:
    root.left = self.deleteNode(root.left, key)