题目链接：https://leetcode-cn.com/problems/delete-node-in-a-bst/
难度：中等

描述：
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：

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

题解

思路：
这里就简单地把待删除结点node的左子树放到node的后继下，而不是采用CLRS中用node的后继来代替node的做法。

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
  9.         if root is None:
  10.             return None
  11.         if root.val > key:
  12.             root.left = self.deleteNode(root.left, key)
  13.         elif root.val < key:
  14.             root.right = self.deleteNode(root.right, key)
  15.         else:
  16.             # 右子节点为空也行
  17.             if root.left is None:
  18.                 return root.right
  19.             elif root.right is None:
  20.                 return root.left
  21.             else:
  22.                 temp = root.right
  23.                 # 找到root的后继
  24.                 while temp.left is not None:
  25.                     temp = temp.left
  26.                 temp.left = root.left
  27.                 return root.right
  28.         return root