Почему это работает
- Каждая четверть — та же задача на квадрате вдвое уже, а одна клетка всегда лист: рекурсия всегда доходит до ответа.
- Квадрат целиком из одного значения ровно тогда, когда все четыре его четверти — листья с этим значением, поэтому хватает проверить четырёх детей: ни одна клетка не смотрится дважды.
- Четверть, где есть оба значения, возвращается узлом, и тогда её родитель тоже остаётся узлом.
Сложность
Время O(n²): каждая клетка один раз становится листом, а каждый квадрат побольше только сравнивает четырёх детей. Память O(log n) сверх самого дерева: стек вызовов глубиной в число делений пополам.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗