LeetCode 427. 建立四叉树思路递归分治 二维前缀和核心思路 对于当前正方形区域判断区域内是否全为 0 或全为 1· 若值统一 → 构造叶子节点isLeaf true。· 若不统一 → 构造内部节点isLeaf false把区域切成四个等大的子正方形按 左上 → 右上 → 左下 → 右下 的顺序递归。判断区域是否统一如果每次遍历整块区域最坏会退化为 O(n² log n)。用二维前缀和可在 O(1) 时间内得到区域和和为 0 说明全是 0和为面积说明全是 1。Java 实现/* // Definition for a QuadTree node. 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, Node _topLeft, Node _topRight, Node _bottomLeft, Node _bottomRight) { val _val; isLeaf _isLeaf; topLeft _topLeft; topRight _topRight; bottomLeft _bottomLeft; bottomRight _bottomRight; } } */classSolution{publicNodeconstruct(int[][]grid){intngrid.length;// 1. 构建二维前缀和pre[i][j] 左上角 (0,0) 到 (i-1,j-1) 的子矩阵和int[][]prenewint[n1][n1];for(inti0;in;i){for(intj0;jn;j){pre[i1][j1]pre[i][j1]pre[i1][j]-pre[i][j]grid[i][j];}}returnbuild(grid,pre,0,0,n);}/** * param r 区域左上角行坐标 * param c 区域左上角列坐标 * param len 区域边长 */privateNodebuild(int[][]grid,int[][]pre,intr,intc,intlen){// O(1) 求区域和intsumpre[rlen][clen]-pre[r][clen]-pre[rlen][c]pre[r][c];// 全 0 或全 1 → 叶子if(sum0||sumlen*len){returnnewNode(grid[r][c]1,true,null,null,null,null);}// 否则切成四个子区域递归inthalflen/2;NodetopLeftbuild(grid,pre,r,c,half);NodetopRightbuild(grid,pre,r,chalf,half);NodebottomLeftbuild(grid,pre,rhalf,c,half);NodebottomRightbuild(grid,pre,rhalf,chalf,half);// 内部节点的 val 无意义随意填 truereturnnewNode(true,false,topLeft,topRight,bottomLeft,bottomRight);}}不用前缀和的暴力版更直观n ≤ 64 也够用classSolution{publicNodeconstruct(int[][]grid){returnbuild(grid,0,0,grid.length);}privateNodebuild(int[][]grid,intr,intc,intlen){if(isUniform(grid,r,c,len)){returnnewNode(grid[r][c]1,true,null,null,null,null);}inthalflen/2;returnnewNode(true,false,build(grid,r,c,half),build(grid,r,chalf,half),build(grid,rhalf,c,half),build(grid,rhalf,chalf,half));}privatebooleanisUniform(int[][]grid,intr,intc,intlen){intvgrid[r][c];for(intir;irlen;i)for(intjc;jclen;j)if(grid[i][j]!v)returnfalse;returntrue;}}复杂度分析版本 时间 空间前缀和版 O(n²)建表 O(n²)每个节点判定 O(1)节点总数 O(n²) O(n²)暴力版 最坏 O(n² log n)每层总共覆盖 n² 格共 log n 层 O(log n) 递归栈注四叉树的节点总数最坏为 (4n² - 1) / 3即 O(n²)所以前缀和版是严格的 O(n²)。关键点递归顺序题目规定孩子顺序为左上、右上、左下、右下构造 Node 时参数顺序千万别写错否则判题判 equals 时失败。叶子判定区域和为 0 或等于 len² 两种都覆盖内部节点的 val 无意义LeetCode 比较时只看 isLeaf 为 false 节点结构不校验 val填 true 即可。边长必为 2 的幂题目保证 n 2^klen / 2 一定整除递归到底时 len 1 必定是叶子不会死递归。切四个孩子前不必单独判断只要区域不统一分治下去各子区域会自行判断是否叶子。