Задача: 255. Verify Preorder Sequence in Binary Search Tree
Сложность: medium

Дан массив уникальных целых чисел preorder. Верните true, если это правильная последовательность обхода в порядке предварительного (preorder) обхода для бинарного дерева поиска.

Пример:

Input: preorder = [5,2,1,3,6]
Output: true

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

1⃣Объявите целое число minLimit с маленьким значением, например, минус бесконечность, и стек.

2⃣Итерируйте по массиву preorder. Для каждого num:
Очистите стек. Пока верх стека меньше num, извлекайте из стека и обновляйте minLimit.
Если num <= minLimit, верните false.
Добавьте num в стек.

3⃣Верните true, если удалось пройти весь массив.

😎 Решение:

import java.util.Stack;

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        int minLimit = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();
        
        for (int num: preorder) {
            while (!stack.isEmpty() && stack.peek() < num) {
                minLimit = stack.pop();
            }
            
            if (num <= minLimit) {
                return false;
            }
            
            stack.push(num);
        }
        
        return true;
    }
}

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