Ссылка на задачу на leetcode: https://leetcode.com/problems/check-completeness-of-a-binary-tree/description/
Условие. Дано двоичное дерево. Нужно проверить его полноту. Полным называется дерево, в котором заполнены все уровни, за исключением быть может только последнего уровня. При этом на последнем уровне все вершины расположены как можно левее.
Пример:
- Полное двоичное дерево.
- Неполное двоичное дерево
Решение. Для решения будем использовать поиск в ширину. Я описал алгоритм поиска в ширину тут: BFS.
Почему поиск в ширину?
Потому что он позволяет обходить граф по слоям. Вначале первую вершину (root), потом всем соседей (в случае с деревом это дети), потом всех соседей соседей (детей всех детей) и т.д. В случае с деревом этот алгоритм будет проходить дерево слой за слоем. И мы можем смотреть на каждый слой, заполнен он или нет так как нам нужно.
Небольшая справка по деревьям.
Граф — это множество вершин и связей между ними.
Дерево — это связный граф, не содержащий циклов. Это древовидная структура, в которой есть корень, которой содержит ноль входящих ребер, а остальные вершины имеют ровно одно входящее ребро.
Двоичное дерево — дерево, в котором каждая вершина имеет не более двух дочерних вершин.
Класс вершины двоичного дерева можно описать на Java следующим образом:
class TreeNode {
int value;
TreeNode left;
TreeNode right;
public TreeNode(int value, TreeNode left, TreeNode right) {
this.value = value;
this.left = left;
this.right = right;
}
}
left и right — это левый и правый ребенок вершины. Для простоты, на собеседованиях можно не объявлять поля private и не использовать геттеры для получения доступа к полям. Это позволит обращаться к полям как node.left, node.right.
Вернемся к задаче.
Как я уже сказал, мы будем использовать BFS. Для случая дерева его можно упростить. Нам не нужно использовать visited. Т.к. мы будем идти от родителей к детям. Вечного цикла у нас не возникнет.
Следующий момент. Нам нужно использовать очередь, в которую можно положить null, чтобы обнаружить случай отсутствия ребенка. В моем описании BFS я использовать ArrayDeque в качестве очереди. Но она не позволяет добавлять null в качестве вершины. Поэтому я буду использовать LinkedList в качестве очереди. Смотри мою статью про коллекции в Java: https://telegra.ph/Ierarhiya-kollekcij-v-Java-05-08
И последний момент. Когда будем обходить дерево по слоям, как только мы нашли отсутствие вершины (null) мы выставим специальный флаг(lastLevel) в true. Если при выставленном флаге lastLevel у нас встретилась не null вершина, значит у нас дерево неполное. Т.е. случай когда был пропуск вершины, а потом снова вершина появилась, как на второй картинке.
Запомните этот трюк с флагом. Он очень часто используется в алгоритмических задачах. Особенно, если в условии есть что-то типа: “все элементы, кроме одного”, “проверить правильность чего-то, но можно одно исправление” и т.д.
Само решение на Java:
class Solution {
public boolean isCompleteTree(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
boolean lastLevel = false;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
lastLevel = true;
continue;
} else if (lastLevel) {
return false;
}
queue.add(node.left);
queue.add(node.right);
}
return true;
}
}
Top comments (0)