Coding interview scrapbook

Дан корень бинарного дерева. Определить, являтеся ли дерево полным. В полном бинарном дереве каждый уровень, за исклением возможно последнего (с листьями), полностью заполен. Если последний уровень не заполнен, то все его элементы занимают все левые позиции. Пример 1: Дано: root = [1,2,3,4,5,6] Результат: true Пояснение: Каждый уровень дерева, за исключением нижнего, заполнен. Самый нижний уровень имеет пробелы только справа. Пример 2: Дано: root = [1,2,3,4,5,null,7] Результат: false Пояснение: Узел с числом 7 следует за "дыркой", которая находится левее его. Ограничения: Количество вершин в дереве находится в интервале [1, 100] . 1 <= Node.val <= 1000 Идея решения Будем обходить дерево по BFS, и на каждом уровне будем добавлять в очередь левое и правое поддерево рассматриваемой вершины, даже если они нулевые.  Если дерево полное, то после рассмотрения всех вершин в очереди останутся только нулевые элементы. В противном случае, дерево не полное, а с "дырками...

Источник: 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...

Дано двоичное дерево, нам нужно установить в его узлах фотокамеры. Камера в каждом узле мониторит сам узел, его родителя и его непосредственных детей. Вычислить минимальное колчиество камер, которыми можно промониторить всё дерево. Пример 1: Дано: [0,0,null,0,0] Результат: 1 Пояснение: Одной камеры достаточно, чтобы промониторить все узлы дерева, если установить её так, как показано на рисунке. Пример 2: Дано: [0,0,null,0,null,0,null,null,0] Результат: 2 Пояснение: По крайней мере 2 камеры нужны, чтобы мониторить всё дерево. На рисунке показана однеа из конфигураций расположения камер. Примечания: Число узлов в дереве варбируется в интервале [1, 1000] . Все узлы дерева имеют значение 0 . Идея решения  Рассмотрим "внутренний" (не корневой и не листовой) узел в дереве. Он может мониториться камерой в родителе, в себе, в своих 2 детях. Итого: 4 узла задействованы. Рассмотрим корневой узел дерева.. Он монтирится двумя детьми и собой. Итого: 3 узла задействованы. Расммотрим...

 Дано бинарное дерево: 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. Сериализованный результат выведен в порядке уровней дерева, где уровни разделены символом #. Внутри уровня его элементы указаны слева направо. Идея решения Нам нужно обойти все "этажи" дерева и выстроить в цепочку элементы дерева, находящиеся на одном "этаже". Самый правый элемент ...