Construct Quad Tree

Средняя№427четыре четверти

Дана сетка n×n из 0 и 1, n — степень двойки. Нужно построить её дерево квадрантов: квадрат из одного значения — лист с этим значением; любой другой квадрат — узел, чьи четыре ребёнка — его левая верхняя, правая верхняя, левая нижняя и правая нижняя четверти. Наша сетка по строкам: 1101, 1111, 0000, 0000 — корень — узел; левая верхняя четверть — лист 1, нижние — листья 0, а правая верхняя — узел с листьями 0, 1, 1, 1.

427 Construct Quad TreeРазбор · 1×

Пример: построить дерево квадрантов сетки 4×4: делим до отдельных клеток, а на обратном пути сливаем четыре одинаковых листа в один.

1101111100000000
клетка, до которой ещё не дошликвадрат текущего вызоватекущий вызовждёт свои четвертипостроено: лист покрывает весь свой квадратчетыре одинаковых листа сливаются в один

Строим дерево для всей сетки 4×4: build(0, 0, 4)

01/53
сначала · назад · пуск · шаг
Скорость
1function construct(grid):
2 return build(0, 0, len(grid))
3
4function build(r, c, size):
5 if size == 1:
6 return leaf(grid[r][c])
7 half = size / 2
8 tl = build(r, c, half)
9 tr = build(r, c + half, half)
10 bl = build(r + half, c, half)
11 br = build(r + half, c + half, half)
12 if tl, tr, bl and br are leaves with one value:
13 return leaf(tl.val)
14 return node(tl, tr, bl, br)
состояние
r
–
c
–
size
–
half
–
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Каждая четверть — та же задача на квадрате вдвое уже, а одна клетка всегда лист: рекурсия всегда доходит до ответа.
  2. Квадрат целиком из одного значения ровно тогда, когда все четыре его четверти — листья с этим значением, поэтому хватает проверить четырёх детей: ни одна клетка не смотрится дважды.
  3. Четверть, где есть оба значения, возвращается узлом, и тогда её родитель тоже остаётся узлом.

Сложность

Время O(n²): каждая клетка один раз становится листом, а каждый квадрат побольше только сравнивает четырёх детей. Память O(log n) сверх самого дерева: стек вызовов глубиной в число делений пополам.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.