Задача: 1008. Construct Binary Search Tree from Preorder Traversal
Сложность: medium

Дается массив целых чисел preorder, который представляет собой обход BST (т.е, гарантируется, что для заданных тестовых случаев всегда можно найти дерево двоичного поиска с заданными требованиями. Дерево двоичного поиска - это двоичное дерево, в котором для каждого узла любой потомок Node.left имеет значение строго меньше, чем Node.val, а любой потомок Node.right имеет значение строго больше, чем Node.val. При обходе бинарного дерева в предварительном порядке сначала выводится значение узла, затем обход Node.left, затем обход Node.right.

Пример:

Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

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

1⃣Инициализация переменных и функций:
Создайте класс узла дерева TreeNode с атрибутами val, left и right.
Инициализируйте индекс, который будет отслеживать текущую позицию в массиве preorder.

2⃣Рекурсивная функция для построения дерева:
Создайте рекурсивную функцию constructBST с аргументами preorder, lower и upper, которые будут ограничивать значения узлов для текущей ветви дерева.
Если текущий индекс выходит за границы массива preorder, верните null.
Получите текущее значение из preorder и проверьте, находится ли оно в пределах допустимого диапазона [lower, upper]. Если нет, верните null.

3⃣Создание узла и рекурсивное построение поддеревьев:
Создайте новый узел с текущим значением и увеличьте индекс.
Рекурсивно вызовите функцию constructBST для создания левого поддерева с обновленным верхним пределом (upper равным значению текущего узла).
Рекурсивно вызовите функцию constructBST для создания правого поддерева с обновленным нижним пределом (lower равным значению текущего узла).
Верните созданный узел.

😎 Решение:

public class Solution {
    private int index = 0;

    public TreeNode bstFromPreorder(int[] preorder) {
        return constructBST(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private TreeNode constructBST(int[] preorder, int lower, int upper) {
        if (index == preorder.length) {
            return null;
        }

        int val = preorder[index];
        if (val < lower || val > upper) {
            return null;
        }

        index++;
        TreeNode root = new TreeNode(val);
        root.left = constructBST(preorder, lower, val);
        root.right = constructBST(preorder, val, upper);
        return root;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

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