Максимальная сумма бинарного дерева

Бинарное дерево — вопросы интервью и практические задачи

А Бинарное дерево представляет собой древовидную структуру данных, в которой каждый узел имеет не более двух дочерних элементов, которые называются левым дочерним элементом и правым дочерним элементом, а самый верхний узел в дереве называется корнем.

В этом посте мы перечислили часто задаваемые вопросы на собеседовании, в которых используется бинарное дерево:

1. Неупорядоченный обход дерева Средний
2. Обход дерева предзаказа Средний
3. Обход дерева постпорядков Средний
4. Проверьте, идентичны ли два бинарных дерева или нет Простой
5. Распечатать вид снизу бинарного дерева Средний
6. Распечатать вид сверху бинарного дерева Средний
7. Преобразование двоичного дерева в его дерево сумм на месте Простой
8. Определить, являются ли заданные узлы бинарного дерева двоюродными братьями друг другу Средний
9. Вывести кузенов данного узла в бинарном дереве Средний
10. Проверить, является ли бинарное дерево деревом сумм или нет Средний
11. Комбинации слов, образованные заменой данных цифр соответствующими алфавитами Жесткий
12. Определить, является ли бинарное дерево поддеревом другого бинарного дерева Средний
13. Найдите диаметр бинарного дерева. Средний
14. Проверить, является ли бинарное дерево симметричным или нет Простой
15. Преобразование бинарного дерева в его зеркало Простой
16. Определите, можно ли преобразовать бинарное дерево в другое, выполнив любое количество обменов дочерними элементами. Простой
17. Найдите наименьшего общего предка (LCA) двух узлов в двоичном дереве Средний
18. Вывести все пути от корня до листовых узлов бинарного дерева Простой
19. Найти предков данного узла в бинарном дереве Средний
20. Найти расстояние между заданными парами узлов в бинарном дереве Жесткий
21. Найдите диагональную сумму бинарного дерева Средний
22. Узлы стока, содержащие ноль, в нижнюю часть бинарного дерева Жесткий
23. Преобразование двоичного дерева в полное дерево путем удаления половинных узлов Средний
24. Обрезать бинарное дерево, чтобы удалить узлы, лежащие на пути, сумма которого меньше k Средний
25. Найдите максимальную сумму от корня до листа в двоичном дереве Средний
26. Проверьте, сбалансировано ли бинарное дерево по высоте или нет Средний
27. Преобразование бинарного дерева в левое дочернее бинарное дерево правого брата Средний
28. Вывести все пути от листа до корневого узла бинарного дерева Средний
29. Итеративно распечатайте путь от листа к корню для каждого листового узла в двоичном дереве. Средний
30. Построить бинарное дерево из родительского массива Жесткий
31. Найти все узлы на заданном расстоянии от листовых узлов в бинарном дереве Жесткий
32. Подсчитайте все поддеревья, имеющие одинаковое значение узлов в двоичном дереве. Средний
33. Найдите максимальную разницу между узлом и его потомками в бинарном дереве Средний
34. Найдите путь максимальной суммы между двумя листьями в бинарном дереве. Жесткий
35. Построить бинарное дерево из обхода в прямом и прямом порядке Жесткий
36. Построить бинарное дерево из обходов в прямом и обратном порядке Жесткий
37. Построить бинарное дерево из последовательностей порядка и порядка уровней Жесткий
38. Построить полное двоичное дерево из последовательности предварительного заказа с информацией о листовых узлах. Жесткий
39. Построить полное бинарное дерево из последовательности предварительного и обратного порядка Жесткий
40. Найдите обратный обход бинарного дерева из его последовательности в прямом и прямом порядке. Средний
41. Установить следующий указатель на неупорядоченный преемник всех узлов в двоичном дереве Простой
42. Найдите обход двоичного дерева в прямом порядке из его последовательности в прямом и обратном порядке. Жесткий
43. Найдите разницу между суммой всех узлов, присутствующих на нечетных и четных уровнях в двоичном дереве. Простой
44. Клонировать бинарное дерево со случайными указателями Жесткий
45. Многопоточное двоичное дерево — обзор и реализация Средний
46. Определите, удовлетворяет ли бинарное дерево свойству сбалансированности высоты красно-черного дерева. Средний
47. Создайте матрицу предков из бинарного дерева Простой
48. Найдите все возможные бинарные деревья, имеющие одинаковый неупорядоченный обход Жесткий
49. Выполнить обход границы на бинарном дереве Средний
50. Проверить, есть ли у каждого узла бинарного дерева ровно один дочерний элемент Простой
51. Оцените двоичное дерево выражений Простой
52. Построение дерева выражений Простой
53. Исправить свойство child-sum в бинарном дереве Средний
54. Максимальная сумма путей в двоичном дереве Жесткий
55. Создайте зеркало м–арного дерева Простой
56. Распечатайте двумерное представление бинарного дерева Простой
57. Построить бинарное дерево из матрицы предков Жесткий
58. Определить, является ли данное бинарное дерево BST или нет Средний
59. Найти преемника по порядку для данного ключа в BST Средний
60. Исправьте двоичное дерево, которое находится всего в одном обмене от превращения в BST. Жесткий
61. Найдите размер наибольшего BST в бинарном дереве Жесткий
62. Распечатать структуру двоичного дерева с его содержимым на C++ Средний
63. Задача о максимальном независимом множестве Средний
64. Алгоритм сжатия кода Хаффмана Жесткий
65. Построить декартово дерево из неупорядоченного обхода Средний
66. Вычислить высоту бинарного дерева с листовыми узлами, образующими круговой двусвязный список Средний
67. Узлы связи присутствуют на каждом уровне бинарного дерева в виде связанного списка Жесткий
68. Преобразование троичного дерева в двусвязный список Средний
69. Извлечь листья бинарного дерева в двусвязный список Средний
70. Найдите вертикальную сумму бинарного дерева Жесткий
71. Преобразование двоичного дерева в двусвязный список на месте Жесткий
72. Проверьте, является ли обход листьев заданных бинарных деревьев одинаковым или нет Жесткий
73. Эффективно печатать все узлы между двумя заданными уровнями в двоичном дереве Простой
74. Вычислить высоту бинарного дерева Простой
75. Удалить бинарное дерево Простой
76. Обход по порядку уровней бинарного дерева Простой
77. Спиральный обход бинарного дерева Средний
78. Обход бинарного дерева в обратном порядке Простой
79. Вывести все узлы идеального бинарного дерева в определенном порядке Жесткий
80. Распечатать левое представление бинарного дерева Простой
81. Найдите следующий узел на том же уровне, что и данный узел в бинарном дереве. Средний
82. Проверить, является ли бинарное дерево полным бинарным деревом или нет Средний
83. Вывести диагональный обход бинарного дерева Средний
84. Распечатайте угловые узлы каждого уровня в бинарном дереве Простой
85. Инвертировать бинарное дерево Простой
86. Преобразование двоичного дерева в двусвязный список по спирали Жесткий
87. Проверьте, является ли бинарное дерево минимальной кучей или нет Средний
88. Инвертировать альтернативные уровни идеального бинарного дерева Жесткий
89. Выполнить вертикальный обход бинарного дерева Средний
90. Вычислить максимальное количество узлов на любом уровне бинарного дерева Простой
91. Вывести правый вид бинарного дерева Средний
92. Найдите минимальную глубину бинарного дерева Простой
93. Поиск в глубину (DFS) и поиск в ширину (BFS) Новичок
94. Вывести узлы бинарного дерева в вертикальном порядке Средний

Также см:

Средний рейтинг 4.9 /5. Подсчет голосов: 104

Голосов пока нет! Будьте первым, кто оценит этот пост.

Сожалеем, что этот пост не оказался для вас полезным!

Расскажите, как мы можем улучшить этот пост?

Спасибо за чтение.

Пожалуйста, используйте наш онлайн-компилятор размещать код в комментариях, используя C, C++, Java, Python, JavaScript, C#, PHP и многие другие популярные языки программирования.

Как мы? Порекомендуйте нас своим друзьям и помогите нам расти. Удачного кодирования 🙂

Этот веб-сайт использует файлы cookie. Используя этот сайт, вы соглашаетесь с использованием файлов cookie, нашей политикой, условиями авторского права и другими условиями. Читайте наши Политика конфиденциальности. Понятно

Источник

Максимальная сумма путей в двоичном дереве

Для заданного бинарного дерева напишите эффективный алгоритм для нахождения максимальной суммы путей между любыми двумя узлами в нем. Путь может начинаться и заканчиваться в любом узле дерева и не должен проходить через корень.

Например, путь максимальной суммы в следующем двоичном дереве выделен зеленым цветом:

Связанный пост:

Мы обсудили нахождение максимальной суммы путей в двоичном дереве, которое начинается и заканчивается конечным узлом, в посте выше. В текущей задаче такого ограничения на то, где путь может начинаться или заканчиваться, нет.

Простым решением было бы пройтись по дереву и для каждого узла вычислить путь максимальной суммы, начинающийся с него и проходящий через его левый и правый потомки. Отслеживайте максимум среди всех найденных путей с максимальной суммой и возвращайте его после обработки всех узлов. Временная сложность этого решения O(n 2 ) , куда n это общее количество узлов в бинарном дереве.

Мы можем уменьшить временную сложность до линейной, обходя дерево снизу вверх. Каждый узел возвращает максимальную сумму пути, “начинающуюся” в этом узле, своему родителю. Чтобы гарантировать, что максимальная сумма путей “начинается” с этого узла, должен быть задействован не более одного потомка узла.

Максимальная сумма путей, проходящих “через” узел, равна максимальному из следующего:

1. Значение узла.
2. Значение узла + максимальная сумма путей, “начиная” с его левого дочернего элемента.
3. Значение узла + максимальная сумма путей, “начиная” с его правого потомка.
4. Значение узла + максимальная сумма путей, “начинающаяся” с его левого дочернего элемента + максимальная сумма путей, “начинающаяся” с его правого дочернего элемента.

Алгоритм может быть реализован следующим образом на C++, Java и Python. Обратите внимание, что максимальная сумма пути передается по ссылке в функцию (вместо ее возврата), и ее значение обновляется внутри функции.

Источник

Найдите путь максимальной суммы между двумя листьями в бинарном дереве.

Для заданного бинарного дерева напишите эффективный алгоритм нахождения максимальной суммы пути между любыми двумя его листьями. Предположим, что бинарное дерево не асимметрично и содержит не менее двух узлов.

Например, максимальный суммарный путь в следующем бинарном дереве равен 22:

Простым решением было бы вычислить максимальную сумму пути от узла к листу от левого и правого дочерних элементов для каждого узла в дереве. Максимальный суммарный путь между двумя листьями, который проходит через узел, имеет значение, равное максимальной сумме пути от узла к листу его левого и правого дочерних элементов плюс значение узла. Наконец, рассмотрим максимальное значение среди всех путей с максимальной суммой, найденных для каждого узла в дереве.

Временная сложность этого решения O(n 2 ) как есть n узлов в дереве, и для каждого узла мы вычисляем максимальную сумму пути от узла к листу его левого и правого поддерева, который занимает O(n) время.

Мы можем решить эту задачу за линейное время, обходя дерево снизу вверх. Вместо вычисления максимального суммарного пути от узла к листу левого и правого дочерних элементов для каждого узла в дереве вычислите максимальный суммарный путь между двумя листьями, который проходит через узел за постоянное время. Идея состоит в том, чтобы начать с нижней части дерева и вернуть максимальную сумму пути от узла к листу для каждого узла до его родителя.

Алгоритм может быть реализован следующим образом на C++, Java и Python. Здесь мы передаем путь максимальной суммы по ссылке на функцию (вместо того, чтобы возвращать ее) и обновляем его значение внутри самой функции, используя возвращаемое значение левого и правого поддеревьев.

Источник

Русские Блоги

LeetCode [124] Бинарное дерево Максимальная сумма пути [C ++, рекурсивный и нерекурсивный]

Описание проблемы:

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Input: [1,2,3] 1 / \ 2 3 Output: 6 

Input: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7 Output: 42

Исходный код:

Проблема дерева, конечно, не рекурсивна. Найдите максимальное значение пути в каждой точке в качестве отправной точки. 86%, пространство 100%.

/** * Definition for a binary tree node. * struct TreeNode < * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) <>* >; */ class Solution < public: int result = INT_MIN; int change(TreeNode* root)< if(!root) return 0; int L = max(change(root->left), 0); int R = max(change(root->right), 0); result = max(result, root->val+L+R); return root->val+max(L,R); > int maxPathSum(TreeNode* root) < if(!root) return 0; change(root); return result; >>;

Существует нерезимо, со стеком с make_pair, имитируют две рекурсивные переменные, но мы только смотрим на метод обхода Travelse сегодня:

Время и пространство такие же, как рекурсивное.

/** * Definition for a binary tree node. * struct TreeNode < * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) <>* >; */ class Solution < public: int maxPathSum(TreeNode* root) < if(!root) return 0; stackst; int result = INT_MIN; st.push(root); TreeNode* pre = NULL; while(!st.empty())< TreeNode* tmp = st.top(); if((!tmp->left && !tmp->right) || (pre && (pre==tmp->left || pre==tmp->right)))< st.pop(); pre = tmp; int L, R; if(tmp->left) L = max(tmp->left->val, 0); if(tmp->right) R = max(tmp->right->val, 0); if(tmp->left && tmp->right)< result = max(result, L + R + tmp->val); tmp->val += max(L, R); > else if(tmp->left)< result = max(result, L + tmp->val); tmp->val += L; > else if(tmp->right)< result = max(result, R + tmp->val); tmp->val += R; > else< result = max(result, tmp->val); > > else< if(tmp->right) st.push(tmp->right); if(tmp->left) st.push(tmp->left); > > return result; > >;

Источник