Данный массив представляет дерево таким образом, что значение массива дает родительский узел этого конкретного индекса. Значение индекса корневого узла всегда будет равно -1. Найдите высоту дерева.
Высота бинарного дерева — это число узлов на пути от корня к самому глубокому листовому узлу, в число которых входят как корень, так и лист.
Input: parent[] = {1 5 5 2 2 -1 3} Output: 4 The given array represents following Binary Tree 5 / \ 1 2 / / \ 0 3 4 / 6 Input: parent[] = {-1, 0, 0, 1, 1, 3, 5}; Output: 5 The given array represents following Binary Tree 0 / \ 1 2 / \ 3 4 / 5 / 6
Источник: Amazon Интервью опыт | Установите 128 (для SDET)
Мы настоятельно рекомендуем свернуть ваш браузер и попробовать это в первую очередь.
Простое решение состоит в том, чтобы сначала построить дерево, а затем найти высоту построенного бинарного дерева. Дерево может быть построено рекурсивно, сначала просматривая текущий корень, затем повторяя найденные индексы и делая их левым и правым поддеревьями корня. Это решение принимает O (n 2 ), так как мы должны линейно искать каждый узел.
Эффективное решение может решить вышеупомянутую проблему за O (n) время. Идея состоит в том, чтобы сначала вычислить глубину каждого узла и сохранить в глубину массива []. Как только у нас есть глубина всех узлов, мы возвращаем максимум всех глубин.
1) Найти глубину всех узлов и заполнить вспомогательный массив глубиной [].
2) Вернуть максимальное значение в глубину [].
Ниже приведены шаги для определения глубины узла по индексу i.
1) Если это корень, глубина [i] равна 1.
2) Если оценивается глубина родителя [i], глубина [i] равна глубине [parent [i]] + 1.
3) Если глубина parent [i] не оценивается, повторите процедуру для parent и присвойте глубину [i] в качестве глубины [parent [i]] + 1 (аналогично описанному выше).
Ниже приводится реализация вышеуказанной идеи.
|
Джава
|
питон
|
C #
|
Выход:
Height is 5
Обратите внимание, что временная сложность этих программ кажется больше, чем O (n). Если мы посмотрим поближе, то увидим, что глубина каждого узла оценивается только один раз.
Эта статья предоставлена Сиддхартом . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме
Рекомендуемые посты:
- Высота n-арного дерева, если указан родительский массив
- Высота родового дерева от родительского массива
- Найти родителя узла в данном двоичном дереве
- Построить двоичное дерево из заданного представления родительского массива
- Найти правильного брата двоичного дерева с указателями родителя
- Построить двоичное дерево из заданного представления родительского массива | Итеративный подход
- Итерационный метод определения высоты двоичного дерева
- Найти высоту специального бинарного дерева, узлы листьев которого связаны
- Сумма всех различий между родителями и детьми в двоичном дереве
- Максимальная сумма родительских детей в двоичном дереве
- Проверьте, сбалансировано ли данное Двоичное Дерево как Красно-Черное Дерево
- Самый низкий общий предок в бинарном дереве | Набор 2 (с помощью родительского указателя)
- Подсчитать все тройки дедушка-родитель-ребенок в двоичном дереве, сумма которого больше X
- Как определить, сбалансировано ли бинарное дерево по высоте?
- Высота бинарного дерева, учитывая только четные уровни
0.00 (0%) 0 votes