450. Delete Node in a BST

Leetcode link

题目简介

/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */

题目给我们一个 BST 的跟 root，要求我们删除其中值为 key 的节点

返回修改后的 BST 的根节点

解题思路

这题我们需要分为两步求解：

1. 找到目标节点
2. 删除目标节点

首先是寻找，这个相对简单，只需要用 DFS 然后根据当前节点与 key 的大小来选择分支即可

删除的部分我们需要分情况来讨论：

1. 如果当前节点没有左右子节点：直接删除
2. 如果当前节点只有左/右节点其一：删除其第一个左/右子节点
3. 如果当前节点的左右子节点都存在：我们需要找到其右子树的最左子节点，用其替代当前节点

Javascript

/**
 * 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) {
    if(!root) {
        return null
    }

    if(key < root.val) {
        root.left = deleteNode(root.left, key)
    } else if(key > root.val) {
        root.right = deleteNode(root.right, key)
    } else {
        // we find it, we delete it
        if(!root.left && !root.right) {
            return null
        }
        if(!root.left) {
            return root.right
        }
        if(!root.right) {
            return root.left
        }
        // use the leftmost node of the right subtree to replace it
        root.val = findMin(root.right)
          // delete the original leftmost node
        root.right = deleteNode(root.right, root.val)
    }
    return root
};

const findMin = node => {
    if(node.left) {
        return findMin(node.left)
    }
    return node.val
}