Sprawdzanie, czy drzewo binarne jest drzewem wyszukiwania binarnego [duplikat]

To pytanie ma już tutaj odpowiedź:

Jak walidować drzewo wyszukiwania binarnego? 30 odpowiedzi

Dzisiaj miałem wywiad, w którym poproszono mnie o napisanie programu, który pobiera drzewo binarne i zwraca prawdę, jeśli jest to również drzewo wyszukiwania binarnego, w przeciwnym razie fałszywe.

Moje podejście1: Przeprowadź przejście w kolejności i zapisz elementy w czasie O (n). Teraz przejrzyj tablicę / listę elementów i sprawdź, czy element w ith indeks jest większy niż element w (i + 1)th indeks. Jeśli taki warunek zostanie napotkany, zwróć fałsz i wyjdź z pętli. (To zajmuje czas O (n)). Na koniec powrót prawdziwy.

Ale ten dżentelmen chciał, żebym zapewnił skuteczne rozwiązanie. Próbowałem, ale nie udało mi się, ponieważ aby sprawdzić, czy jest to BST, muszę sprawdzić każdy węzeł.

Ponadto wskazywał mi na myślenie o rekursji. Moje podejście 2: BT jest BST, jeśli dla dowolnego węzła N N-> lewy jest <N i N-> prawy> N, a następca w kolejności lewego węzła N jest mniejszy niż N, a następca w kolejności prawego węzła N jest większa niż N, a lewe i prawe poddrzewa są BST.

Ale będzie to skomplikowane, a czas pracy nie wydaje się być dobry. Pomóż, jeśli znasz jakieś optymalne rozwiązanie.

questionAnswers(7)

yourAnswerToTheQuestion