题目

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

  1. 首先找到需要删除的节点；
  2. 如果找到了，删除它。

说明： 要求算法时间复杂度为 Delete Node in a BST - 图1，h 为树的高度。

示例:

  1. root = [5,3,6,2,4,null,7]
  2. key = 3
  4.     5
  5.    / \
  6.   3   6
  7.  / \   \
  8. 2   4   7
  10. 给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
  12. 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
  14.     5
  15.    / \
  16.   4   6
  17.  /     \
  18. 2       7
  20. 另一个正确答案是 [5,2,6,null,4,null,7]。
  22.     5
  23.    / \
  24.   2   6
  25.    \   \
  26.     4   7

方案一

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root:
            return None
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
        else:
            # 叶子节点
            if not root.left and not root.right:
                root = None
            elif root.left: # 存在前驱节点
                pre = self.precursor(root)
                root.val = pre.val
                root.left = self.deleteNode(root.left, pre.val)
            else:
                succ = self.successor(root)
                root.val = succ.val
                root.right = self.deleteNode(root.right, succ.val)
        return root

    def precursor(self, root) -> TreeNode:
        '''找到前驱节点，不存在返回None'''
        if not root or not root.left:
            return None
        else:
            node = root.left
            while node.right:
                node = node.right
            return node

    def successor(self, root) -> TreeNode:
        '''找到后继节点，不存在返回None'''
        if not root or not root.right:
            return None
        else:
            node = root.right
            while node.left:
                node = node.left
            return node

原文

https://leetcode-cn.com/explore/learn/card/introduction-to-data-structure-binary-search-tree/65/basic-operations-in-a-bst/180/

https://leetcode-cn.com/problems/delete-node-in-a-bst/solution/shan-chu-er-cha-sou-suo-shu-zhong-de-jie-dian-by-l/