Псевдокод для нерекурсивной реализации высоты дерева и isBST

Question

Я нахожусь в процессе преобразования рекурсивной функции для BST в нерекурсивную, чтобы помочь подготовиться к собеседованию.До сих пор я разобрался с предварительным заказом, заказом, заказом, поиском, удалением, вставкой и преобразованием BST в круговой связанный список.У меня возникают проблемы с выяснением, как использовать стек или очереди, чтобы получить высоту и узнать, является ли это BST.Любые советы будут с благодарностью.Я не ищу код, но логика кода.

Answer 1

Для начала, отличная работа по подготовке к таким интервью!Я надеюсь, что вам весело играть с этими алгоритмами.

Давайте начнем с попытки определить, является ли двоичное дерево BST.Один из способов сделать это - выполнить обход дерева по порядку и проверить, находятся ли элементы в отсортированном порядке.Это будет верно, если и только если дерево является BST.Поскольку у вас уже есть код для обхода элементов дерева по порядку, вы должны иметь возможность легко адаптировать свой код, чтобы проверить, отсортированы ли элементы, выходящие из обхода по порядку, отслеживая последний элемент, который вы видели вобход по порядку, затем сравнение каждого сгенерированного элемента с предыдущим элементом.Если они не в порядке, дерево не является BST.

Чтобы определить высоту дерева, можно выбрать любой из выполненных вами поисков (предварительный заказ)., postorder, inorder) и отслеживать высоту стека в каждой точке.Идея заключается в том, что, поскольку ваш стек всегда будет отслеживать путь от любого узла до корня, вы можете просто пройтись по дереву и записать самое глубокое, что вы когда-либо видели в стеке.Эта максимальная глубина равна высоте дерева.

Надеюсь, это поможет!И удачи в интервью!

Answer 2

Чтобы найти высоту дерева, вы можете использовать обход Морриса [O (n) time]].

Чтобы проверить, является ли это действительным BST, выполните обход дерева по порядку.Переместить элементы в массив.Проверьте, отсортирован ли массив или нет для проверки BST.