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

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function (root, key) {
    // 二叉搜索树特点
    // 1.左节点<父节点<右节点
    // 2.根节点大于左子树的所有节点
    // 3.根节点小于右子树的所有节点

    if (!root) {
        return null
    }
    if (root.val === key && root.left === null && root.right === null) { // 直接删除根节点
        return null
    }

    // 先找到要删除的节点
    let cur = root
    let parent = null // 父节点
    while (cur) {
        if (key < cur.val) {
            parent = cur
            cur = cur.left
        } else if (key > cur.val) {
            parent = cur
            cur = cur.right
        } else if (key === cur.val) { // 找到了
            // 有3种情况

            // 1.待删除节点为叶子节点：只需把父节点原来指向该节点的链指向null。
            if (cur.left === null && cur.right === null) {
                if (parent === null) { // parent为null，说明删除的是根节点
                    return null
                }
                if (cur.val < parent.val) {
                    parent.left = null
                } else {
                    parent.right = null
                }
                break
            }

            // 2.待删除节点的左节点或右节点为null：只需把父节点原来指向该节点的链指向剩下的左节点或右节点。
            if (cur.left === null) { // 左节点为null
                if (parent === null) { // parent为null，说明删除的是根节点
                    return cur.right // 直接返回右子树
                }
                if (cur.val < parent.val) {
                    parent.left = cur.right
                } else {
                    parent.right = cur.right
                }
                break
            }
            if (cur.right === null) { // 右节点为null
                if (parent === null) { // parent为null，说明删除的是根节点
                    return cur.left // 直接返回左子树
                }
                if (cur.val < parent.val) {
                    parent.left = cur.left
                } else {
                    parent.right = cur.left
                }
                break
            }

            // 3.待删除节点的左右节点都存在：
            // (1)找到该节点的左子树的最大值节点 或 右子树的最小值节点，下面以右子树最小值为例
            // (2)把最小值赋值给该节点
            // (3)删除最小值节点
            // (4)删除最小值节点后，右子树的根节点可能发生变化，当前节点要重新连接右子树的根节点
            if (cur.left !== null && cur.right !== null) {
                const minNode = getMinNode(cur.right) // 找到右子树最小值节点
                cur.val = minNode.val // 最小值先存起来
                cur.right = deleteNode(cur.right, minNode.val) // 删除最小值节点
                break
            }
        }
    }

    return root
};

/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function (root, key) {
    if (!root) { // 递归结束条件
        return null
    }

    // 递归找到待删除的节点然后删除
    if (key < root.val) {
        // 往左子树找，删除节点后左子树的根节点可能发生变化，所以需要把当前节点连接新的左子树根节点
        root.left = deleteNode(root.left, key)
        return root
    } else if (key > root.val) {
        // 往右子树找，删除节点后右子树的根节点可能发生变化，所以需要重新连接新的右子树根节点
        root.right = deleteNode(root.right, key)
        return root
    } else if (key === root.val) { // 找到了
        // 3种情况
        // 第1种：待删除节点为叶子节点，只需把父节点指向该节点的链指向null
        // 第2种：待删除节点左节点或右节点为null，只需把父节点指向该节点的链指向剩下的左子树或右子树
        // 第3种：待删除节点的左右节点都存在
        // (1)找到待删除节点 左子树的最大值节点 或 右子树的最小值节点；以右子树最小值节点为例
        // (2)将最小值节点的val赋值给当前节点
        // (3)然后删除最小值节点(采用递归)
        // (4)删除最小值节点后，右子树根节点可能发生变化，当前节点应重新连接新的右子树根节点
        if (root.left === null && root.right === null) {
            return null
        } else if (root.left === null) {
            return root.right
        } else if (root.right === null) {
            return root.left
        } else if (root.left && root.right) {
            let minNode = getMinNode(root.right)
            root.val = minNode.val
            root.right = deleteNode(root.right, minNode.val)
            return root
        }
    }
}

/**
 * 获取最小值节点
 * @param {TreeNode} root 
 */
function getMinNode(root) {
    // 最小值在最左下角
    let cur = root
    while (cur.left !== null) {
        cur = cur.left
    }
    return cur
}