Сообщения

Показаны сообщения с ярлыком "Деревья"

Время для оповещения всех сотрудников

Изображение
  1376 .   Time Needed to Inform All Employees В компании работаю т n сотрудников, каждый с уникальным ID от 0 до n - 1 . У главы компании ID= headID . У каждого работника есть менеджер, заданный в массиве manager , где manager[i] - это менеджер сотрудника с индексом i ,   manager[headID] = -1 . Также отношения субординации представляют собой дерево. Глава компании хочет известить всех сотрудников срочными новостями. Он передает новость своим прямым субординатам, а те - своим.И так далее, пока все сотрудники не получат эту новость. Сотруднику с индексом i треубуется informTime[i] минут, чтобы известить своих субординатов. То есть после informTime[i] минут, все его субординаты начнут передавать новость дальше. Вернуть число минут, которые нужны, чтобы известить всех сотрудников. Пример 1: Дано: n = 1, headID = 0, manager = [-1], informTime = [0] Результат: 0 Пояснение: Глава компании - единственный сотрудник. Пример 2: Дано: n = 6, headID = 2, manager = [2,...

Взвешенная сумма вложенного списка

Источник: https://leetcode.com/problems/nested-list-weight-sum-ii/ Дан вложенный список целых чисел. Подсчитать сумму всех его элементов, взвешенных их глубиной. Каждый элемент вложенного списка может быть целым числом или вложенным списком - тоже состоящий из целых чисел и вложенных списков. Вес увеличивается снизу вверх, то есть "листьевые" целые элементы имеют вес 1. А корень имеет наибольший вес. Как изменится алгоритм, если вес увеличивается от корня к листьям? Пример 1: Дано: [[1,1],2,[1,1]] Результат: 8 Пояснение: Четыре единицы находятся на глубине 1, а 2 - на глубине 2 . Поэтому сумма считается: 1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8. Пример 2: Дано: [1,[4,[6]]] Результат: 17 Поясненеи: Число 1 находится на глубине 3, 4 - на глубине 2, 6 - на глубине 1. Поэтому сумма считается: 1*3 + 4*2 + 6*1 = 17. Есть некоторый класс NestedInteger, со следующим интерфейсом: /**  * // Интерфейс для вложенного списка, не нужно его имплементировать  *  * public interface NestedIn...

Следующий правый указатель в каждой вершине дерева

Изображение
 Дано бинарное дерево: struct Node { int val; Node *left; Node *right; Node *next; } Заполнить поле next так, чтобы вершина дерева указывала на соседнюю вершину справа, если та существует. Если же никакой вершины справа не существует, то указательnext принимает значение NULL. Изначально все next указатели имеют значение NULL. Ограничение: можно использовать константный объём (не зависящий от размера лерева) дополнительной памяти. Пример: Дано: root = [1,2,3,4,5,null,7] Результат: [1,#,2,3,#,4,5,7,#] Объяснение: Исходное бинарное дерево на рисунке A. Результат на рисунке B: каждая вершина указывает на соседа справа, если он существует. А если не существует, то указывает на NULL. Сериализованный результат выведен в порядке уровней дерева, где уровни разделены символом #. Внутри уровня его элементы указаны слева направо. Идея решения Нам нужно обойти все "этажи" дерева и выстроить в цепочку элементы дерева, находящиеся на одном "этаже". Самый правый элемент ...

Поисковое дерево с возрастающими значениям

Задача. Дано бинарное поисковое дерево. Реорганизовать его в порядке in_order таким образом, чтобы самый левый (наименьший, поскольку это бинарное поисковое дерево) ребенок стал корнем, чтобы у любой вершины не было левого ребенка, но был только правый ребенок. Пример: Дано: [5,3,6,2,4,null,8,1,null,null,null,7,9] 5 / \ 3 6 / \ \ 2 4 8  / / \ 1 7 9 Результат: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9] 1   \   2   \   3   \   4   \   5   \   6   \   7   \   8   \ 9 Примечания: У каждого вдерева вершин 1 до 100. У каждой вершины значения варьируются от 0 до 1000. /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *  ...