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

Difficulty
Medium
Tags
二叉树
二叉搜索树
URL
https://leetcode-cn.com/problems/delete-node-in-a-bst/
Star
❤
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
  1. 首先找到需要删除的节点；
  1. 如果找到了，删除它。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
示例:
root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

    5
   / \
  4   6
 /     \
2       7

另一个正确答案是 [5,2,6,null,4,null,7]。

    5
   / \
  2   6
   \   \
    4   7

法1 递归

思路
先找到要删除的节点，再删除该节点。
查找：查找的时候利用二叉搜索树的性质。查找框架如下：
def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
      # 找到了
      if root.val == key:
          # 删除该节点

      # 向右查找
      elif root.val < key:
					# 返回删除后的右子树
          root.right = self.deleteNode(root.right, key)
      # 向左查找
      else:
					# 返回删除后的左子树
          root.left = self.deleteNode(root.left, key)
        
      return root
删除：删除分为三种情况：
  • 待删除节点为叶子节点：直接删除即可
      • notion imagenotion image
  • 待删除节点有一个子节点：将该子节点移到待删除节点位置
      • notion imagenotion image
  • 待删除节点拥有两个子节点：为了不破坏 BST 的性质，A必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己。本题解采用后者
      • notion imagenotion image
实现
采用递归的方式，站在某一棵子树根节点上（该子树会有父节点，但并不关心该子树根节点是在父节点左边还是右边）,判断该根节点值与key的大小：
  1. 如果 a.val < key， 说明待删除节点应该在右子树，那么此时返回完成删除操作后的右子树,并接到a的右边，对于a的父节点，返回a即可
a.right = self.delateNode(a.right, key) return aa.right = self.delateNode(a.right, key) return a
a.right = self.delateNode(a.right, key) return a
2. 如果 a.val > key， 说明待删除节点应该在左子树，那么此时返回完成删除操作后的左子树,并接到a的左边，对于a的父节点，返回a即可
a.left= self.delateNode(a.left, key) return aa.left= self.delateNode(a.left, key) return a
a.left= self.delateNode(a.left, key) return a
3. 如果a.val == key ，说明找到待删除的节点了，此时执行删除操作。
  • 如果待删除节点为叶子节点，那么直接返回None 即可
notion imagenotion image
  • 如果待删除节点存在一个子节点，那么直接将该子节点返回
notion imagenotion image
  • 如果待删除节点存在两个子节点，那么为了保证二叉搜索树的中序遍历递增性质，需要找左子树中最右节点或者右子树中最左节点来替换当前节点。分别成称为前驱和后继节点替换有两种策略
      1. 一种是只交换val,然后删除m节点，如下图
      找到右子树中最小的节点和a交换，且返回新的a找到右子树中最小的节点和a交换，且返回新的a
      找到右子树中最小的节点和a交换，且返回新的a
      2. 第二种是改变节点指向。
    • 首先令m节点的父节点指向m的右子节点，此操作是把m节点架空了
    • 其次将m节点左右子节点分别指向当前a的左右节点
    • 最后返回m节点给a的父节点
      • if a.val == key:
		parentNode = root
    minNode = root.right
    while minNode.left:
		    parentNode = minNode
		    minNode = minNode.left
     # 找到右子树中的最小节点了，且 parentNode 为最小节点的父节点
     # 此时需要判断 最小节点是不是就是root的右子节点
     if parentNode is not root:
          parentNode.left = minNode.right
          minNode.right = root.right
     minNode.left = root.left
     return minNode
题解
# 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: TreeNode, key: int) -> TreeNode:
        if root is None:
            return None
        # 找到了
        if root.val == key:
            # 叶子节点
            if root.left is None and root.right is None:
                return None
            # 有一个子节点
            elif root.left is None or root.right is None:
                if root.left:
                    return root.left
                else:
                    return root.right
            # 有两个子节点
            elif root.left and root.right:
                minNode = self.searchMinNode(root.right)
								# 实际应用中，应该是交换这两个节点的指针，而不能简单重置val
                root.val = minNode.val
                root.right = self.deleteNode(root.right, minNode.val)


        # 向右查找
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
        # 向左查找
        else:
            root.left = self.deleteNode(root.left, key)
        
        return root

    def searchMinNode(self, node):
        # 最左边的就是最小的
        while node.left:
            node = node.left
        return node
上述代码是修改了待删除节点的val，且把替换的节点删掉了，而没有修改节点本身的地址。
以下代码是真实删除节点
# 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: TreeNode, key: int) -> TreeNode:
        if root is None:
            return
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
            return root
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
            return root
            
        else:
            if root.left is None and root.right is None:
                return None
            elif root.left is None or root.right is None:
                if root.left:
                    return root.left
                else:
                    return root.right
            else:
                # 右子树中最小的节点
                parentNode = root
                minNode = root.right
                while minNode.left:
                    parentNode = minNode
                    minNode = minNode.left
                # 找到右子树中的最小节点了，且 parentNode 为最小节点的父节点
                # 此时需要判断 最小节点是不是就是root的右子节点
                if parentNode is not root:
                    parentNode.left = minNode.right
                    minNode.right = root.right
                minNode.left = root.left
                return minNode
        
        
    def searchMinNode(self, node):
        while node.left:
            node = node.left
        return node
通俗易懂版本
# 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]:
        if root is None:
            return None

        if root.val < key:
            root.right = self.deleteNode(root.right, key)
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        else:
            if root.left is None and root.right is None:
                return None
            elif root.left is None:
                return root.right
            elif root.right is None:
                return root.left
            else:
                # 找左子树的最大值
                # 定位到左子树上
                left_tree = root.left

                # 左子树没有右节点
                if left_tree.right is None:
                    left_tree.right = root.right
                    return left_tree
                else:
                    # 左子树有右节点
                    prev = left_tree
                    cur = prev.right
                    while cur and cur.right:
                        prev = cur
                        cur = cur.right
                    prev.right = cur.left
                    cur.right = root.right
                    cur.left = left_tree

                    return cur

        return root