Задача: 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⃣Если у узла pесть правое поддерево:
Ищем самый левый ((наименьший) узел в этом поддереве — это и будет преемник.

2⃣Если правого поддерева нет:
Запускаем в порядке обхода от root, отслеживаем предыдущий узел. Если предыдущий узел — это p, то текущий — наш преемник.

3⃣При обходе обновляем previous, если преемник найден — сохраняем его в inorderSuccessorNode.

😎 Решение:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    private TreeNode previous = null;
    private TreeNode inorderSuccessorNode = null;

    public TreeNode InorderSuccessor(TreeNode root, TreeNode p) {
        if (p.right != null) {
            TreeNode leftmost = p.right;
            while (leftmost.left != null) {
                leftmost = leftmost.left;
            }
            inorderSuccessorNode = leftmost;
        } else {
            InorderCase2(root, p);
        }
        return inorderSuccessorNode;
    }

    private void InorderCase2(TreeNode node, TreeNode p) {
        if (node == null) {
            return;
        }

        InorderCase2(node.left, p);

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

        previous = node;

        InorderCase2(node.right, p);
    }
}

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