1
const deleteNode = function (root, key) {
2
  if (root == null) return root
3

4
  if (root.val > key) {
5
    // 往左子树找
6
    root.left = deleteNode(root.left, key)
7
  } else if (root.val < key) {
8
    // 往右子树找
9
    root.right = deleteNode(root.right, key)
10
  } else {
11
    // 找到了
12
    if (!root.left && !root.right) {
13
      // 待删除的节点左右子树均为空。证明是叶子节点，直接删除即可
14
      root = null
15
    } else if (root.left && !root.right) {
16
      // 待删除的节点右子树为空，让待删除节点的左子树替代自己。
17
      root = root.left
18
    } else if (!root.left && root.right) {
19
      // 待删除的节点左子树为空，让待删除节点的右子树替代自己。
20
      root = root.right
21
    } else if (root.left && root.right) {
22
      // 如果待删除的节点的左右子树都不为空。我们需要找到比当前节点小的最大节点（前驱）来替换自己
23
      let last = root.left
24
      while (last.right) {
25
        last = last.left
26
      }
27
      // 最终的last就是比当前节点小的最大节点，将值进行替换
28
      root.val = last.val
29
      // 删除该最大节点
30
      root.left = deleteNode(root.left, last.val)
31
    }
32
  }
33
  return root
34
}