Бинарное дерево — вопросы интервью и практические задачи
А Бинарное дерево представляет собой древовидную структуру данных, в которой каждый узел имеет не более двух дочерних элементов, которые называются левым дочерним элементом и правым дочерним элементом, а самый верхний узел в дереве называется корнем.
В этом посте мы перечислили часто задаваемые вопросы на собеседовании, в которых используется бинарное дерево:
- Неупорядоченный обход дерева Средний
- Обход дерева предзаказа Средний
- Обход дерева постпорядков Средний
- Проверьте, идентичны ли два бинарных дерева или нет Простой
- Распечатать вид снизу бинарного дерева Средний
- Распечатать вид сверху бинарного дерева Средний
- Преобразование двоичного дерева в его дерево сумм на месте Простой
- Определить, являются ли заданные узлы бинарного дерева двоюродными братьями друг другу Средний
- Вывести кузенов данного узла в бинарном дереве Средний
- Проверить, является ли бинарное дерево деревом сумм или нет Средний
- Комбинации слов, образованные заменой данных цифр соответствующими алфавитами Жесткий
- Определить, является ли бинарное дерево поддеревом другого бинарного дерева Средний
- Найдите диаметр бинарного дерева. Средний
- Проверить, является ли бинарное дерево симметричным или нет Простой
- Преобразование бинарного дерева в его зеркало Простой
- Определите, можно ли преобразовать бинарное дерево в другое, выполнив любое количество обменов дочерними элементами. Простой
- Найдите наименьшего общего предка (LCA) двух узлов в двоичном дереве Средний
- Вывести все пути от корня до листовых узлов бинарного дерева Простой
- Найти предков данного узла в бинарном дереве Средний
- Найти расстояние между заданными парами узлов в бинарном дереве Жесткий
- Найдите диагональную сумму бинарного дерева Средний
- Узлы стока, содержащие ноль, в нижнюю часть бинарного дерева Жесткий
- Преобразование двоичного дерева в полное дерево путем удаления половинных узлов Средний
- Обрезать бинарное дерево, чтобы удалить узлы, лежащие на пути, сумма которого меньше k Средний
- Найдите максимальную сумму от корня до листа в двоичном дереве Средний
- Проверьте, сбалансировано ли бинарное дерево по высоте или нет Средний
- Преобразование бинарного дерева в левое дочернее бинарное дерево правого брата Средний
- Вывести все пути от листа до корневого узла бинарного дерева Средний
- Итеративно распечатайте путь от листа к корню для каждого листового узла в двоичном дереве. Средний
- Построить бинарное дерево из родительского массива Жесткий
- Найти все узлы на заданном расстоянии от листовых узлов в бинарном дереве Жесткий
- Подсчитайте все поддеревья, имеющие одинаковое значение узлов в двоичном дереве. Средний
- Найдите максимальную разницу между узлом и его потомками в бинарном дереве Средний
- Найдите путь максимальной суммы между двумя листьями в бинарном дереве. Жесткий
- Построить бинарное дерево из обхода в прямом и прямом порядке Жесткий
- Построить бинарное дерево из обходов в прямом и обратном порядке Жесткий
- Построить бинарное дерево из последовательностей порядка и порядка уровней Жесткий
- Построить полное двоичное дерево из последовательности предварительного заказа с информацией о листовых узлах. Жесткий
- Построить полное бинарное дерево из последовательности предварительного и обратного порядка Жесткий
- Найдите обратный обход бинарного дерева из его последовательности в прямом и прямом порядке. Средний
- Установить следующий указатель на неупорядоченный преемник всех узлов в двоичном дереве Простой
- Найдите обход двоичного дерева в прямом порядке из его последовательности в прямом и обратном порядке. Жесткий
- Найдите разницу между суммой всех узлов, присутствующих на нечетных и четных уровнях в двоичном дереве. Простой
- Клонировать бинарное дерево со случайными указателями Жесткий
- Многопоточное двоичное дерево — обзор и реализация Средний
- Определите, удовлетворяет ли бинарное дерево свойству сбалансированности высоты красно-черного дерева. Средний
- Создайте матрицу предков из бинарного дерева Простой
- Найдите все возможные бинарные деревья, имеющие одинаковый неупорядоченный обход Жесткий
- Выполнить обход границы на бинарном дереве Средний
- Проверить, есть ли у каждого узла бинарного дерева ровно один дочерний элемент Простой
- Оцените двоичное дерево выражений Простой
- Построение дерева выражений Простой
- Исправить свойство child-sum в бинарном дереве Средний
- Максимальная сумма путей в двоичном дереве Жесткий
- Создайте зеркало м–арного дерева Простой
- Распечатайте двумерное представление бинарного дерева Простой
- Построить бинарное дерево из матрицы предков Жесткий
- Определить, является ли данное бинарное дерево BST или нет Средний
- Найти преемника по порядку для данного ключа в BST Средний
- Исправьте двоичное дерево, которое находится всего в одном обмене от превращения в BST. Жесткий
- Найдите размер наибольшего BST в бинарном дереве Жесткий
- Распечатать структуру двоичного дерева с его содержимым на C++ Средний
- Задача о максимальном независимом множестве Средний
- Алгоритм сжатия кода Хаффмана Жесткий
- Построить декартово дерево из неупорядоченного обхода Средний
- Вычислить высоту бинарного дерева с листовыми узлами, образующими круговой двусвязный список Средний
- Узлы связи присутствуют на каждом уровне бинарного дерева в виде связанного списка Жесткий
- Преобразование троичного дерева в двусвязный список Средний
- Извлечь листья бинарного дерева в двусвязный список Средний
- Найдите вертикальную сумму бинарного дерева Жесткий
- Преобразование двоичного дерева в двусвязный список на месте Жесткий
- Проверьте, является ли обход листьев заданных бинарных деревьев одинаковым или нет Жесткий
- Эффективно печатать все узлы между двумя заданными уровнями в двоичном дереве Простой
- Вычислить высоту бинарного дерева Простой
- Удалить бинарное дерево Простой
- Обход по порядку уровней бинарного дерева Простой
- Спиральный обход бинарного дерева Средний
- Обход бинарного дерева в обратном порядке Простой
- Вывести все узлы идеального бинарного дерева в определенном порядке Жесткий
- Распечатать левое представление бинарного дерева Простой
- Найдите следующий узел на том же уровне, что и данный узел в бинарном дереве. Средний
- Проверить, является ли бинарное дерево полным бинарным деревом или нет Средний
- Вывести диагональный обход бинарного дерева Средний
- Распечатайте угловые узлы каждого уровня в бинарном дереве Простой
- Инвертировать бинарное дерево Простой
- Преобразование двоичного дерева в двусвязный список по спирали Жесткий
- Проверьте, является ли бинарное дерево минимальной кучей или нет Средний
- Инвертировать альтернативные уровни идеального бинарного дерева Жесткий
- Выполнить вертикальный обход бинарного дерева Средний
- Вычислить максимальное количество узлов на любом уровне бинарного дерева Простой
- Вывести правый вид бинарного дерева Средний
- Найдите минимальную глубину бинарного дерева Простой
- Поиск в глубину (DFS) и поиск в ширину (BFS) Новичок
- Вывести узлы бинарного дерева в вертикальном порядке Средний
Также см:
Средний рейтинг 4.9 /5. Подсчет голосов: 104
Голосов пока нет! Будьте первым, кто оценит этот пост.
Сожалеем, что этот пост не оказался для вас полезным!
Расскажите, как мы можем улучшить этот пост?
Спасибо за чтение.
Пожалуйста, используйте наш онлайн-компилятор размещать код в комментариях, используя C, C++, Java, Python, JavaScript, C#, PHP и многие другие популярные языки программирования.
Как мы? Порекомендуйте нас своим друзьям и помогите нам расти. Удачного кодирования 🙂
Этот веб-сайт использует файлы cookie. Используя этот сайт, вы соглашаетесь с использованием файлов cookie, нашей политикой, условиями авторского права и другими условиями. Читайте наши Политика конфиденциальности. Понятно
Источник
how to find the height of a node in binary tree recursively
this is my sample code for find the Height, is defined as the length of the longest path by number of nodes from self to a leaf. The height of a leaf node is 1. it doesn’t work.
Actually, I just need an algorithm. Because, my code doesn’t work. And if you know the solution, maybe pseudo code 😛
@thg435 My guess is: «why doesn’t it work?» The poster seems to be struggling with English, so I would give him a break here. That being said, I wouldn’t give the code (since it looks like a homework to me), but explain some of the more blatant mistakes that he made.
@TGulmammadov: two options. Option 1: draw a tree on a piece of paper and try to find the height for any given node manually. Note your steps. Try to describe what you’re doing first in pseudocode and then in python. Option 2: sit back and wait for some nice guy to post the codez for you.
Do you have an example where it fails? How does it fail? Let me guess: it always counts the depth of the leftmost path, not of arbitrary paths?
6 Answers 6
What you’re doing isn’t recursive, it’s iterative. Recursive would be something like:
def height(node): if node is None: return 0 else: return max(height(node.left), height(node.right)) + 1 return max(height(node.left), height(node.right)) + 1 returns a value >= 1 however leaf nodes have height zero. @mata Could you please clarify. Thanks.
@harishvc — Looking at the edit history, I had return -1 , which means a leaf would have a height of 0 (which is usually how the hight of a tree is defined), but the OP specified «The height of a leaf node is 1», so that’s probably why I changed it.
A leaf node will have None for node.left and node.right , therefore ending the recursion there, there’s no need to treat leaf or inner or root nodes differently.
@Illusionist — for any node the height ist the height of it’s largest child tree (that’s what the max function does) + 1. For a leaf node where both node.left and node.right are None heigh will return 0 for both and the recursion ends there.
You were given the solution by mata, but I suggest you also look at your code and understand what it is doing:
while self.right != None: self = self.right path = path +1 What will this do? it will find the right child, then its right child, and so on. So this checks only one path of the «rightmost» leaf.
This does the same for the left:
while self.left != None: self = self.left path = path +1 The idea in recursion is that for each subproblem, you solve it using the exact same recipe for all other subproblems. So if you would apply your algorithm only to a subtree or a leaf, it would still work.
Also, a recursive definition calls itself (although you can implement this with a loop, but that is beyond the scope here).
Recursion: see definition of Recursion.
Источник
Вычислить высоту бинарного дерева с листовыми узлами, образующими круговой двусвязный список
Напишите алгоритм для вычисления высоты двоичного дерева с конечными узлами, формирующими круговой двусвязный список, в котором левый и правый указатели листового узла будут действовать как предыдущий и следующий указатели циклического двусвязного списка соответственно.
Например, рассмотрим следующее бинарное дерево. Листовые узлы 7, 5 и 6 соединены с помощью левого и правого указателей и образуют круговой двусвязный список.
Мы знаем, что высота бинарного дерева это общее количество узлов, присутствующих на самом длинном пути от корня до конечного узла. Идея состоит в том, чтобы обойти дерево в мода на заказ и вычислить высоту левого и правого поддерева. Высота поддерева с корнем в любом узле будет на единицу больше, чем максимальная высота его левого и правого поддеревьев. Рекурсивно примените это свойство ко всем узлам дерева восходящим образом (в обратном порядке) и верните максимальную высоту поддерева с корнем в этом узле.
Для типичных бинарных деревьев левый и правый потомки конечного узла являются нулевыми указателями. Но здесь левый и правый потомки листовых узлов действуют как предыдущий и следующий указатели циклического двусвязного списка. Чтобы узел был конечным узлом, проверьте, указывают ли его левое право и правое лево на сам узел.
Этот подход демонстрируется ниже на C, Java и Python:
Источник