题目描述
思路解析动画文字版
记住「全同就缩成叶子,不全同就切四块各自递归」,下面每一帧都在套它。
检查 整个网格:左上角 (0,0)、边长 4 的这块,里面的数字是不是全一样?
这块有 0 也有 1、不全同 → 不能缩,折半成四块:左上、右上、左下、右下,每块各自递归。
检查 整个网格的左上:左上角 (0,0)、边长 2 的这块,里面的数字是不是全一样?
这块全是 1,全同 → 缩成一个叶子,值就是 1(蓝色标出)。
检查 整个网格的右上:左上角 (0,2)、边长 2 的这块,里面的数字是不是全一样?
这块全是 0,全同 → 缩成一个叶子,值就是 0(蓝色标出)。
检查 整个网格的左下:左上角 (2,0)、边长 2 的这块,里面的数字是不是全一样?
这块有 0 也有 1、不全同 → 不能缩,折半成四块:左上、右上、左下、右下,每块各自递归。
检查 整个网格的左下的左上:左上角 (2,0)、边长 1 的这块,里面的数字是不是全一样?
这块只有一个格子,1 → 缩成一个叶子,值就是 1(蓝色标出)。
检查 整个网格的左下的右上:左上角 (2,1)、边长 1 的这块,里面的数字是不是全一样?
这块只有一个格子,0 → 缩成一个叶子,值就是 0(蓝色标出)。
检查 整个网格的左下的左下:左上角 (3,0)、边长 1 的这块,里面的数字是不是全一样?
这块只有一个格子,0 → 缩成一个叶子,值就是 0(蓝色标出)。
检查 整个网格的左下的右下:左上角 (3,1)、边长 1 的这块,里面的数字是不是全一样?
这块只有一个格子,1 → 缩成一个叶子,值就是 1(蓝色标出)。
检查 整个网格的右下:左上角 (2,2)、边长 2 的这块,里面的数字是不是全一样?
这块全是 1,全同 → 缩成一个叶子,值就是 1(蓝色标出)。
整张网格解析完毕:左上、右上、右下三块各缩成一个叶子,左下那块切成了四个单格叶子。蓝色就是最终所有叶子覆盖的区域。
复盘一下整棵四叉树的结构:根是内部节点,挂着左上(叶 1)、右上(叶 0)、左下、右下(叶 1)四个孩子。这一帧先画出根和四个孩子,其中左下是内部节点;下一帧再补上它递归出来的四个叶子。
左下这个内部节点再挂上它四个单格叶子(1、0、0、1),四叉树就建完了。回头看:全同的大块只用一个叶子表示,省掉了一整片重复格子,这正是四叉树压缩网格的价值。
边界:全同则整棵就一个叶子;单格即叶子;最碎的情况切到单格为止。
两个高频追问:四叉树每个内部节点四个孩子;同值大块缩成一个叶子省空间。
参考代码
from typing import Listclass Node: def __init__(self, val, isLeaf, topLeft=None, topRight=None, bottomLeft=None, bottomRight=None): self.val = val self.isLeaf = isLeaf self.topLeft = topLeft self.topRight = topRight self.bottomLeft = bottomLeft self.bottomRight = bottomRightclass Solution: def construct(self, grid: List[List[int]]) -> 'Node': n = len(grid) def build(r, c, size): first = grid[r][c] same = all(grid[i][j] == first for i in range(r, r + size) for j in range(c, c + size)) if same: return Node(bool(first), True) h = size // 2 return Node(True, False, build(r, c, h), build(r, c + h, h), build(r + h, c, h), build(r + h, c + h, h)) return build(0, 0, n)复杂度
- 时间：O(n² log n)，递归共 log n 层,每一层所有区域合起来要扫完整张网格、约 n² 个格子做全同判断,故每层 O(n²)、共 log n 层
- 空间：O(log n)，只算递归栈深度,等于递归层数 log n;返回的四叉树本身不计入额外空间
易错点
面试追问把动画讲成自己的话
追问四叉树和普通二叉树有什么不同?
追问为什么能压缩、能省空间?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
N 叉树的层序遍历
LeetCode 429 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题