Выяснение, является ли двоичное дерево двоичным деревом поиска [дубликат]
На этот вопрос уже есть ответ здесь:
Сегодня у меня было интервью, где меня попросили написать программу, которая берет двоичное дерево и возвращает true, если оно также является двоичным деревом поиска, иначе false.
Мой подход1: выполнить обход по порядку и сохранить элементы за время O(n). Теперь просмотрите массив/список элементов и проверьте, больше ли элемент с индексом i th, чем элемент с индексом (i+1) th. Если такое условие встречается, верните false и прервите цикл. (Это занимает O(n) времени). В конце вернуть true.
Но этот джентльмен хотел, чтобы я предложил эффективное решение. Я пытался, но безуспешно, потому что, чтобы определить, является ли это BST, мне нужно проверить каждый узел.
Кроме того, он указывал мне подумать над рекурсией. Мой подход 2: BT является BST, если для любого узла N N->left right > N , а последовательный преемник левого узла N меньше N, а последовательный преемник правого узла N больше, чем N, а левое и правое поддеревья являются BST.
Но это будет сложно, и время выполнения не кажется хорошим. Пожалуйста, помогите, если вы знаете какое-либо оптимальное решение.