题目

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

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

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

示例 1: image.png

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。 image.png

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3:

输入: root = [], key = 0
输出: []

提示:

节点数的范围 [0, 104].
-105 <= Node.val <= 10^5
节点值唯一
root 是合法的二叉搜索树
-105 <= key <= 10^5

进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/delete-node-in-a-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

二叉搜索树的基本操作，删除比较复杂。针对要删除节点的子节点个数的不同，需要分三种情况。

第一种情况是，如果要删除的节点没有子节点，只需要直接将父节点中，指向要删除节点的指针置为 null 。

第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。

第三种情况是，如果要删除的节点有两个子节点。需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点，所以，我们可以应用上面两条规则来删除这个最小节点。

代码

  1. class Solution {
  2.     public TreeNode deleteNode(TreeNode root, int key) {
  3.         // p指向要删除的节点，初始化指向根节点
  4.         TreeNode p = root;
  5.         //  pp记录的是p的父节点
  6.         TreeNode pp = null;
  7.         while (p != null) {
  8.             if (p.val > key) {
  9.                 pp = p;
  10.                 p = p.left;
  11.             } else if (p.val < key) {
  12.                 pp = p;
  13.                 p = p.right;
  14.             } else {
  15.                 // 进入这里就说明找到了要删除的节点
  16.                 // 要删除的节点有两个子节点，查找右子树中最小节点
  17.                 if (p.left != null && p.right != null) {
  18.                     // 右子树中最小节点
  19.                     TreeNode q = p.right;
  20.                     // q的父节点
  21.                     TreeNode qq = p;
  22.                     while (q.left != null) {
  23.                         qq = q;
  24.                         q = q.left;
  25.                     }
  26.                     // 将最小节点的值赋给要删除位置的节点中
  27.                     p.val = q.val;
  28.                     // 更改p和pp指向，转为删除q，就可以通用下面的逻辑了
  29.                     p = q;
  30.                     pp = qq;
  31.                 }
  32.                 // 删除节点是叶子节点或者仅有一个子节点
  33.                 TreeNode child = null;
  34.                 if (p.left != null) {
  35.                     child = p.left;
  36.                 } else {
  37.                     child = p.right;
  38.                 }
  39.                 // 注意这里，pp可能为null，说明删除的是根节点
  40.                 if (pp == null) {
  41.                     root = child;
  42.                 } else if (pp.left == p) { // 删除的节点p是其父节点pp的左孩子，将p的孩子挂到pp上，下面right同理
  43.                     pp.left = child;
  44.                 } else {
  45.                     pp.right = child;
  46.                 }
  47.                 // 这里要返回，不然可能无法结束循环
  48.                 return root;
  49.             }
  50.         }
  51.         // 没有找到指定的删除节点
  52.         return root;
  53.     }
  54. }