LeetCode 427中等树/分治
建立四叉树 图解题解
这道题到底在问什么
给定 n×n(n 为 2 的幂)的 0/1 网格 grid,构造四叉树:某区域若全为同一值则建成叶子节点(isLeaf=true、val=该值);否则建成内部节点,并把区域等分成左上、右上、左下、右下四个子区域分别递归。返回根节点。
- 输入
- grid=[[0]]
- 输出
- 一个 val=false 的叶子
- 输入
- grid=[[1,0],[0,1]]
- 输出
- 内部根 + 4 个叶子
最优解：一步一步想明白
- 3记住「全同就缩成叶子,不全同就切四块各自递归」,下面每一帧都在套它。
- 4检查 整个网格:左上角 (0,0)、边长 4 的这块,里面的数字是不是全一样?
- 5这块有 0 也有 1、不全同 → 不能缩,折半成四块:左上、右上、左下、右下,每块各自递归。
- 6检查 整个网格的左上:左上角 (0,0)、边长 2 的这块,里面的数字是不是全一样?
- 7这块全是 1,全同 → 缩成一个叶子,值就是 1(蓝色标出)。
- 8检查 整个网格的右上:左上角 (0,2)、边长 2 的这块,里面的数字是不是全一样?
- 9这块全是 0,全同 → 缩成一个叶子,值就是 0(蓝色标出)。
- 10检查 整个网格的左下:左上角 (2,0)、边长 2 的这块,里面的数字是不是全一样?
- 11这块有 0 也有 1、不全同 → 不能缩,折半成四块:左上、右上、左下、右下,每块各自递归。
- 12检查 整个网格的左下的左上:左上角 (2,0)、边长 1 的这块,里面的数字是不是全一样?
- 13这块只有一个格子,1 → 缩成一个叶子,值就是 1(蓝色标出)。
- 14检查 整个网格的左下的右上:左上角 (2,1)、边长 1 的这块,里面的数字是不是全一样?
- 15这块只有一个格子,0 → 缩成一个叶子,值就是 0(蓝色标出)。
- 16检查 整个网格的左下的左下:左上角 (3,0)、边长 1 的这块,里面的数字是不是全一样?
- 17这块只有一个格子,0 → 缩成一个叶子,值就是 0(蓝色标出)。
- 18检查 整个网格的左下的右下:左上角 (3,1)、边长 1 的这块,里面的数字是不是全一样?
- 19这块只有一个格子,1 → 缩成一个叶子,值就是 1(蓝色标出)。
- 20检查 整个网格的右下:左上角 (2,2)、边长 2 的这块,里面的数字是不是全一样?
- 21这块全是 1,全同 → 缩成一个叶子,值就是 1(蓝色标出)。
- 22整张网格解析完毕:左上、右上、右下三块各缩成一个叶子,左下那块切成了四个单格叶子。蓝色就是最终所有叶子覆盖的区域。
- 23复盘一下整棵四叉树的结构:根是内部节点,挂着左上(叶 1)、右上(叶 0)、左下、右下(叶 1)四个孩子。这一帧先画出根和四个孩子,其中左下是内部节点;下一帧再补上它递归出来的四个叶子。
- 24左下这个内部节点再挂上它四个单格叶子(1、0、0、1),四叉树就建完了。回头看:全同的大块只用一个叶子表示,省掉了一整片重复格子,这正是四叉树压缩网格的价值。
⚠️ 容易写错的地方
✗ 错：判断全同时只看四个角
✓ 对：必须扫遍整块每个格子
角相同不代表中间也相同,漏扫会把不该缩的块错缩成叶子
✗ 错：四个子区域坐标算错
✓ 对：左上(r,c)、右上(r,c+h)、左下(r+h,c)、右下(r+h,c+h)
行偏 r+h、列偏 c+h,横竖偏移别搞反,否则切错块
✗ 错：忘了单格是递归出口
✓ 对：size=1 时必然全同,直接返回叶子
不处理会无限递归;其实折半到 1 自然全同、自动停下
完整代码（Python / C++ / Java）
Python
from typing import List
class 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 = bottomRight
class 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)C++
#include <vector>
using namespace std;
class Node {
public:
bool val;
bool isLeaf;
Node* topLeft;
Node* topRight;
Node* bottomLeft;
Node* bottomRight;
Node() : val(false), isLeaf(false), topLeft(nullptr), topRight(nullptr), bottomLeft(nullptr), bottomRight(nullptr) {}
Node(bool _val, bool _isLeaf) : val(_val), isLeaf(_isLeaf), topLeft(nullptr), topRight(nullptr), bottomLeft(nullptr), bottomRight(nullptr) {}
Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) : val(_val), isLeaf(_isLeaf), topLeft(_topLeft), topRight(_topRight), bottomLeft(_bottomLeft), bottomRight(_bottomRight) {}
};
class Solution {
public:
Node* construct(vector<vector<int>>& grid) { return build(grid, 0, 0, grid.size()); }
Node* build(vector<vector<int>>& g, int r, int c, int size) {
int first = g[r][c]; bool same = true;
for (int i = r; i < r + size; ++i) for (int j = c; j < c + size; ++j) if (g[i][j] != first) same = false;
if (same) return new Node(first == 1, true);
int h = size / 2;
return new Node(true, false, build(g,r,c,h), build(g,r,c+h,h), build(g,r+h,c,h), build(g,r+h,c+h,h));
}
};Java
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
public Node() {}
public Node(boolean _val, boolean _isLeaf) { val = _val; isLeaf = _isLeaf; }
public Node(boolean _val, boolean _isLeaf, Node _topLeft, Node _topRight, Node _bottomLeft, Node _bottomRight) {
val = _val; isLeaf = _isLeaf; topLeft = _topLeft; topRight = _topRight; bottomLeft = _bottomLeft; bottomRight = _bottomRight;
}
}
class Solution {
public Node construct(int[][] grid) { return build(grid, 0, 0, grid.length); }
private Node build(int[][] g, int r, int c, int size) {
int first = g[r][c];
boolean same = true;
for (int i = r; i < r + size; i++) for (int j = c; j < c + size; j++) if (g[i][j] != first) same = false;
if (same) return new Node(first == 1, true);
int h = size / 2;
return new Node(true, false, build(g, r, c, h), build(g, r, c + h, h), build(g, r + h, c, h), build(g, r + h, c + h, h));
}
}复杂度
时间
O(n² log n)
递归共 log n 层,每一层所有区域合起来要扫完整张网格、约 n² 个格子做全同判断,故每层 O(n²)、共 log n 层
空间
O(log n)
只算递归栈深度,等于递归层数 log n;返回的四叉树本身不计入额外空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 建立四叉树 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
四叉树和普通二叉树有什么不同?+
普通二叉树每个节点最多两个孩子;四叉树每个内部节点恰好有四个孩子(左上、右上、左下、右下),对应把一个正方形区域等分成四个小正方形。它天然适合表示二维空间的层级划分,比如图像压缩、地图分块。
为什么能压缩、能省空间?+
一整块值相同的大区域,四叉树只用一个叶子就表示了,不必为每个格子都建节点。网格里同值的连片区域越大,压缩效果越明显;极端情况整张全同,一个叶子就够。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 建立四叉树 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。