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

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

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

递归

  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 = (ri
  7.  ght===undefined ? null : right)
  8.  * }
  9.  */
  10. /**
  11.  * @param {TreeNode} root
  12.  * @param {number} key
  13.  * @return {TreeNode}
  14.  */
  15. var deleteNode = function (root, key) {
  16.     if (root === null)
  17.         return root;
  18.     if (root.val === key) {
  19.         if (!root.left)
  20.             return root.right;
  21.         else if (!root.right)
  22.             return root.left;
  23.         else {
  24.             let cur = root.right;
  25.             while (cur.left) {
  26.                 cur = cur.left;
  27.             }
  28.             cur.left = root.left;
  29.             root = root.right;
  30.             return root;
  31.         }
  32.     }
  33.     if (root.val > key)
  34.         root.left = deleteNode(root.left, key);
  35.     if (root.val < key)
  36.         root.right = deleteNode(root.right, key);
  37.     return root;
  38. };

迭代

  1. var deleteNode = function (root, key) {
  2.     const deleteOneNode = target => {
  3.         if (!target) return target
  4.         if (!target.right) return target.left
  5.         let cur = target.right
  6.         while (cur.left) {
  7.             cur = cur.left
  8.         }
  9.         cur.left = target.left
  10.         return target.right
  11.     }
  13.     if (!root) return root
  14.     let cur = root
  15.     let pre = null
  16.     while (cur) {
  17.         if (cur.val === key) break
  18.         pre = cur
  19.         cur.val > key ? cur = cur.left : cur = cur.right
  20.     }
  21.     if (!pre) {
  22.         return deleteOneNode(cur)
  23.     }
  24.     if (pre.left && pre.left.val === key) {
  25.         pre.left = deleteOneNode(cur)
  26.     }
  27.     if (pre.right && pre.right.val === key) {
  28.         pre.right = deleteOneNode(cur)
  29.     }
  30.     return root
  31. }