450. Delete Node in a BST

Задача

Даны корень BST и ключ. Удалите узел с этим ключом и верните корень обновлённого BST.

Примеры

Пример 1

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]

Пояснение

Удаляем узел со значением 3. Один из вариантов — [5,4,6,2,null,null,7]; также принимается [5,2,6,null,4,null,7].

Пример 2

Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]

Пояснение

В дереве нет узла со значением 0.

Пример 3

Input: root = [], key = 0
Output: []

Решение

Решение

/**
 * Удаляет узел со значением `key` из BST и возвращает (возможно новый) корень.
 *
 * Сложность по времени: O(h), где h — высота дерева.
 * - Поиск удаляемого узла идёт по одному пути вниз (сравнения key с root.val), это O(h).
 * - Если у узла 2 ребёнка, мы дополнительно ищем inorder successor: минимум в правом поддереве (идём вправо 1 раз, затем “влево до упора”), это тоже O(h) в худшем случае.
 * - Затем удаляем successor рекурсивно в правом поддереве; это ещё один проход по высоте, но суммарно всё равно остаётся O(h) (константное число проходов по высоте). 
 * - В несбалансированном дереве h может быть n, поэтому худший случай по времени — O(n); в сбалансированном — O(log n).
 *
 * Сложность по памяти: O(h) из-за глубины рекурсии (стек вызовов).
 * - В худшем случае O(n) для “списка”, в сбалансированном O(log n).
 */
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 {
        if (!root.left) return root.right;
        if (!root.right) return root.left;
 
        // ВАЖНО: здесь должен быть let, потому что переменную мы двигаем по дереву
        let newNode = root.right;
        while (newNode.left) {
            newNode = newNode.left;
        }
 
        root.val = newNode.val;
        root.right = deleteNode(root.right, newNode.val);
    }
 
    return root;
};