Lstmxx的空间

450. 删除二叉搜索树中的节点

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

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

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

链接

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
  if (root === null) return null;
  if (key > root.val) root.right = deleteNode(root.right, key);
  else if (key < root.val) root.left = deleteNode(root.left, key)
  else if (root.left !== null && root.right !== null) {
    // 通过右子树的右子树来替换
    if (root.right.left === null) {
      root.val = root.right.val
      root.right = root.right.right
    } else {
      // 找出右子树最小的值（即最左子树），用它来替换此时的节点，并把最小值的右子树接到最小值的父节点上
      let min = root.right
      let minParent = root
      while(min.left !== null) {
        minParent = min
        min = min.left
      }
      root.val = min.val
      minParent.left = min.right
    }
  } else {
    root = root.left ? root.left : root.right
  }
  return root
};