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

本文最后更新于：2022年10月28日下午

题目描述

第一张图
第二张图

思路和实现

二叉搜索树，即二叉查找树，Binary Search Tree，简称BST。在BST中，给定节点左子树里的节点会小于给定节点，而右子树里的节点会大于给定节点。
那么我们需要在满足约束的情况下进行删除，就需要特别的策略，以下给出我的策略的描述：（P.S：看题目的示例有两种答案，那么你也应该知道策略不止一种）

迭代找到要删除的节点，以及它的父节点
如果被删除的节点有左右子树，那么应该用被删除节点的左子树的最大元素节点来替代这个被删除节点

根据BST的约束，我们可以知道被删除节点的左子树中的最大元素节点应该是该子树最右边的节点，迭代找出这个节点和它的父节点
如果这个最大元素节点就是被删除节点的左子节点，那么需要把该左子节点的左子节点挂在它的父节点的左子节点上
如果这个最大元素节点不是被删除节点的左子节点，那么要把这个最大元素节点的父节点的右子节点指向该最大元素节点的左子节点
上述操作完成后，将该最大元素节点左右子树的引用改为删除节点左右子树的引用
如果被删除的节点只有左子树或者右子树，那么只需要把被删除节点的父节点指向被删除节点的引用指向这个被删除节点的左子树或右子树即可
如果被删除的节点没有左右子树，把它的父节点指向它的引用改为None即可
最开始的实现：

# 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 deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        current, parent = root, None
        while current and current.val != key:  # 找到要删除的节点，以及它的父节点
            parent = current
            current = current.left if current.val > key else current.right
        if current is None:  # 不存在该节点
            return root
        elif current.left is not None and current.right is not None:  # 如果被删除节点拥有左右子节点，找到左子树中的最大节点current
            successor, successor_parent = current.left, current
            while successor.right:  # 遍历到最右后，就找到了最大节点
                successor_parent = successor
                successor = successor.right
            if successor_parent.val == current.val:  # 如果这个最大元素节点就是被删除节点的左子节点，那么需要把该左子节点的左子节点挂在它父节点的左子节点上
                successor_parent.left = successor.left
            else:  # 如果这个最大元素节点不是被删除节点的左子节点，那么要把这个最大元素节点的父节点的右子节点指向该最大元素节点的左子节点
                successor_parent.right = successor.left
            successor.left = current.left
            successor.right = current.right
            current = successor
        else:
            if current.left is None:
                current = current.right
            elif current.right is None:
                current = current.left
            else:
                current = None
        if parent is None:
            return current
        elif parent.left and parent.left.val == key:
            parent.left = current
        else:
            parent.right = current
        return root

优化后：

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        current, parent = root, None
        while current and current.val != key:
            parent = current
            current = current.left if current.val > key else current.right
        if current is None:
            return root
        if current.left is None and current.right is None:
            current = None
        elif current.left is None:
            current = current.right
        elif current.right is None:
            current = current.left
        else:
            successor, successor_parent = current.left, current
            while successor.right:
                successor_parent = successor
                successor = successor.right
            if successor_parent.val == current.val:
                successor_parent.left = successor.left
            else:
                successor_parent.right = successor.left
            successor.left = current.left
            successor.right = current.right
            current = successor
        if parent is None:
            return current
        elif parent.left and parent.left.val == key:
            parent.left = current
        else:
            parent.right = current
        return root