删除二叉搜索树中的节点

LeetCode-450 💫

// 参考题解: https://leetcode-cn.com/problems/delete-node-in-a-bst/solution/tu-jie-di-gui-shi-xian-shan-chu-er-cha-s-70l8/
var deleteNode = function(root, key) {
  if (root === null) return null
  if (root.val > key) {
    // 节点值大于key，说明key在左子树
    root.left = deleteNode(root.left, key)
  } else if (root.val < key) {
    // 节点值小于key，说明key在右子树
    root.right = deleteNode(root.right, key)
  } else {
    /* 找到节点后的处理 */
    // 情况1/2：不存在左右子树(末端节点) || 只存在左子树/右右子树
    // 左子树为空，直接返回右子树
    if (root.left === null) return root.right
    // 右子树为空，直接返回左子树
    if (root.right === null) return root.left

    // 情况3：左右子树都存在，找出该节点右子树的最小节点
    let temp = root.right // 获取目标节点的右子树根节点
    while (temp.left) temp = temp.left // 拿到右子树的最左侧节点
    temp.left = root.left // 最左侧节点left指向目标节点的左侧(接上)

    // 返回右子树
    return root.right
  }
  return root
}