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