Задача: 285. Inorder Successor in BST
Сложность: medium

Дан корень бинарного дерева поиска и узел p в нем. Верните преемника этого узла в порядке возрастания в бинарном дереве поиска (BST). Если у данного узла нет преемника в порядке возрастания в дереве, верните null.
Преемник узла p — это узел с наименьшим ключом, который больше p.val.

Пример:

Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.

👨‍💻 Алгоритм:

1⃣Определение переменных класса:
Определите две переменные класса: previous и inorderSuccessorNode. Переменная previous будет использоваться при обработке второго случая, а inorderSuccessorNode будет содержать результат, который нужно вернуть.

2⃣Обработка двух случаев:
В функции inorderSuccessor сначала проверьте, какой из двух случаев нужно обработать, проверяя наличие правого дочернего элемента.
Правый дочерний элемент существует:
- присвойте правый дочерний элемент узлу leftmost и итерируйтесь, пока не достигнете узла (leftmost), у которого нет левого дочернего элемента. Итерируйте, присваивая leftmost = leftmost.left, пока не получите левый узел в поддереве.
Правый дочерний элемент не существует:
- определите функцию inorderCase2 и передайте ей узел и узел p.
- выполните простой обход в порядке возрастания: сначала рекурсируйте на левый дочерний элемент узла.
- когда рекурсия вернется, проверьте, равна ли переменная класса previous узлу p. Если это так, значит p является предшественником узла, или, другими словами, узел является преемником узла p. Назначьте inorderSuccessorNode узлу и вернитесь из функции.
- наконец, верните inorderSuccessorNode как результат.

3⃣Итерация и обновление:
В функции inorderCase2 обновляйте previous текущим узлом и продолжайте рекурсировать на правый дочерний элемент.

😎 Решение:

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class Solution {
    constructor() {
        this.previous = null;
        this.inorderSuccessorNode = null;
    }

    inorderSuccessor(root, p) {
        if (p.right !== null) {
            let leftmost = p.right;
            while (leftmost.left !== null) {
                leftmost = leftmost.left;
            }
            this.inorderSuccessorNode = leftmost;
        } else {
            this.inorderCase2(root, p);
        }
        return this.inorderSuccessorNode;
    }

    inorderCase2(node, p) {
        if (node === null) {
            return;
        }

        this.inorderCase2(node.left, p);

        if (this.previous === p && this.inorderSuccessorNode === null) {
            this.inorderSuccessorNode = node;
            return;
        }

        this.previous = node;

        this.inorderCase2(node.right, p);
    }
}

Ставь 👍 и забирай 📚 Базу знаний