题目

题目来源：力扣（LeetCode）

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

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

首先找到需要删除的节点；
如果找到了，删除它。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。

示例:

root = [5,3,6,2,4,null,7]
key = 3

  1. 5<br />   / \<br />  3   6<br /> / \   \<br />2   4   7

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

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

  1. 5<br />   / \<br />  4   6<br /> /     \<br />2       7

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

  1. 5<br />   / \<br />  2   6<br />   \   \<br />    4   7

思路分析

二叉搜索树具有以下性质：

  1. 若任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；
  2. 若任意节点的右子树不为空，则右子树上所有子节点的值均大于它的根节点的值；
  3. 任意节点的左、右子树也分别为二叉搜索树；

根据二叉搜索树的性质：

  • 如果要删除的目标节点大于当前节点的值，说明要删除的目标节点在右子树中，去右子树中寻找目标节点
  • 如果要删除的目标节点小于当前节点的值，说明要删除的目标节点在左子树中，去左子树中寻找目标节点
  • 找到了要删除的目标节点，则分为三种情况：
    • 若要删除的目标节点没有子节点，即删除的目标节点是一个叶子节点，则直接删除即可
    • 若要删除的目标节点只有一个左孩子或只有一个右孩子，让子节点接替自己的位置即可
    • 若要删除的目标节点既有左孩子又有右孩子，为了不破坏二叉搜索树的性质，必须在被删除节点的左子树中找到最大的那个节点，或者在右子树中找到最小的节点来接替自己
  • 如果没有没有找到要删除的目标节点，则直接返回 null

代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @param {number} key
  12.  * @return {TreeNode}
  13.  */
  14. var deleteNode = function (root, key) {
  15.   // 传入的节点 node 为 null，说明键不存在于树中，直接返回 null
  16.   if (root == null) {
  17.     return null;
  18.   }
  19.   // 要删除的目标节点小于当前节点值，根据二叉搜索树的性质，去左子树中删除目标节点
  20.   if (key < root.val) {
  21.     root.left = deleteNode(root.left, key);
  22.   }
  24.   // 要删除的目标节点大于当前节点值，根据二叉搜索树的性质，去右子树中删除目标节点
  25.   else if (key > root.val) {
  26.     root.right = deleteNode(root.right, key);
  27.   }
  29.   // 找到了要删除的目标节点，则需要处理三种情况
  30.   // 第一种：移除一个叶节点
  31.   // 第二种：移除一个有左侧或右侧子节点的节点
  32.   // 第三种：移除有两个子节点的的节点
  33.   else {
  35.     // 移除一个叶节点（没有左侧子节点和右侧子节点）
  36.     if (root.left == null && root.right == null) {
  37.       // 将 节点 赋值为 null 来移除它
  38.       root = null;
  39.       // 返回 null 来将当前移除节点对应的父节点指针赋予 null 值
  40.       return root;
  41.     }
  42.     //当前节点没有左子树
  43.     else if (root.left == null) {
  44.       return root.right;
  45.     }
  46.     //当前节点没有右子树
  47.     else if (root.right == null) {
  48.       return root.left;
  49.     }
  50.     //当前节点既有左子树又有右子树
  51.     else {
  52.       let node = root.right;
  53.       //找到当前节点右子树最左边的叶子结点
  54.       while (node.left != null) {
  55.         node = node.left;
  56.       }
  57.       //将root的左子树放到root的右子树的最下面的左叶子节点的左子树上
  58.       node.left = root.left;
  59.       return root.right;
  60.     }
  61.   }
  62.   return root;
  63. }

详情解析前往：https://www.yuque.com/moozi/lu64iw/tbamba#p91bZ