LeetCode 427. 建立四叉树

2026-03-28 HGNULB 约 10 分钟

文章信息 3 个分类 4 个标签

分类

题目描述

✅ 427. 建立四叉树

题意分析

题目目标：给一个 $n \times n$ 的 01 矩阵（$n$ 是 2 的幂），把它压缩成四叉树。若某个正方形区域内的值全部相同，就用一个叶节点表示（isLeaf = true，val 记录那个值）；否则建一个内部节点（isLeaf = false），把区域等分成四个子正方形，分别递归构建 topLeft、topRight、bottomLeft、bottomRight。

核心约束：$n$ 是 2 的幂这一条至关重要——它保证每次对半切分都能整除，永远不会出现 $3 \times 3$ 切成两半这样的尴尬，因此递归的终止条件只可能是「区域同质」或「区域缩到单格」，不需要处理奇数边长。另外题面明确说明内部节点的 val 取什么值都不影响判题，所以不必为它纠结。

边界处理：$n = 1$ 时整个矩阵就是一个格子，必然是叶节点；全 0 或全 1 的大矩阵会在根节点直接收敛成一个叶子；四个子区域的下标范围必须严丝合缝地覆盖原区域，不重不漏。

实现取舍：判断「区域是否同质」有两种做法——直接扫描该区域的每个格子（实现简单，但整体复杂度是 $O(n^2 \log n)$），或者预处理二维前缀和后 $O(1)$ 判断（整体降到 $O(n^2)$）。面试里先给扫描版本把结构写对，再把前缀和优化说出来即可。

解法：树形遍历

核心思路

这题的形状天然就是分治：「构建区域 $R$ 的四叉树」这个问题，要么直接有答案（区域同质），要么可以被拆成四个规模减半的同类子问题。所以递归函数的签名必须能描述任意一个正方形区域，这里用左上角 $(a, b)$ 与右下角 $(c, d)$ 四个坐标来表达，而不是「起点 + 边长」——两者等价，四坐标写法在切分时下标更直白。

递归的语义要钉死：dfs(a, b, c, d) 返回以该矩形区域为内容的四叉树的根节点。有了这个定义，父节点只需要把四个子调用的返回值挂上去，不需要关心子树内部长什么样，这是分治能层层展开的前提。

终止条件不是「区域缩到 $1 \times 1$」，而是「区域内的值全部相同」——这才是题目的压缩语义，也是四叉树能省空间的原因。单格区域必然同质，所以它是这个条件的特例，不需要单独写。

判断同质的技巧值得一提：代码用 zero 和 one 两个标志位（而不是计数器）记录区域内是否出现过 0 和是否出现过 1，最后 zero + one == 1 就说明只出现了其中一种，即区域同质。同时 one == 1 直接告诉我们那个唯一的值是不是 1，于是 val = isLeaf && one == 1 一行同时处理了叶节点取值和内部节点取默认值两件事。

切分的下标是全题最容易出错的地方。设行中点 midRow = (a + c) / 2、列中点 midCol = (b + d) / 2，则四个子区域分别是：左上 $[a, midRow] \times [b, midCol]$、右上 $[a, midRow] \times [midCol+1, d]$、左下 $[midRow+1, c] \times [b, midCol]$、右下 $[midRow+1, c] \times [midCol+1, d]$。不变量是四个子区域两两不交且并集恰为原区域——midRow 与 midRow + 1 首尾相接，这正是「不重不漏」的保证。因为 $n$ 是 2 的幂且区间是闭区间，每次切分后的边长恰好减半，不会出现空区域。

解题步骤

第一步：入口调用 dfs(0, 0, n - 1, n - 1)，用闭区间描述整个矩阵。 为什么用闭区间：切分时 mid 与 mid + 1 天然衔接，比半开区间少一次减一的心智负担。

第二步：在 dfs 里遍历区域内所有格子，用 zero、one 两个标志位记录出现过哪些值。 为什么用标志位而不是计数：我们只关心「有没有」而不关心「有几个」，标志位让后面的 zero + one == 1 这个判据成立，写法更紧凑。

第三步：isLeaf = (zero + one == 1)。 为什么这样判：两个标志位之和为 1 意味着恰好只有一种值出现过，即区域同质；为 2 说明 0 和 1 都出现了，必须继续细分。

第四步：val = isLeaf && one == 1，据此建节点。 为什么把 isLeaf 也写进去：内部节点的 val 按题意可以任取，统一置成 false 最省事；这行写法顺带完成了这件事，不必再写一个分支。

第五步：若 isLeaf 为真，直接返回该叶节点。 为什么可以立刻返回：压缩语义在这里达成，继续细分虽然结果等价但会产生冗余节点，判题不接受。

第六步：否则依次递归四个子区域并挂到对应指针上，最后返回内部节点。 为什么顺序是左上、右上、左下、右下：题目对四个孩子的语义有明确规定，顺序写错会得到一棵「形状对但内容错位」的树。

以 grid = [[0, 1], [1, 0]] 走一遍：入口是 dfs(0, 0, 1, 1)。

扫描区域 $[0,1] \times [0,1]$ 的四个格子：grid[0][0] = 0 让 zero = 1，grid[0][1] = 1 让 one = 1，grid[1][0] = 1 与 grid[1][1] = 0 不改变标志位。zero + one = 2 ≠ 1，所以 isLeaf = false，val = false。建内部节点，继续切分。

计算中点：midRow = (0 + 1) / 2 = 0，midCol = (0 + 1) / 2 = 0。四个子区域分别是 $[0,0] \times [0,0]$、$[0,0] \times [1,1]$、$[1,1] \times [0,0]$、$[1,1] \times [1,1]$——恰好是四个单格，两两不交且并起来正是整个 $2 \times 2$，不变量成立。

topLeft = dfs(0, 0, 0, 0)：只扫到 grid[0][0] = 0，zero = 1、one = 0，zero + one = 1 故 isLeaf = true；val = true && (one == 1)，而 one = 0，所以 val = false。返回叶节点 [false, true]。

topRight = dfs(0, 1, 0, 1)：扫到 grid[0][1] = 1，one = 1、zero = 0，isLeaf = true，val = true。返回 [true, true]。

bottomLeft = dfs(1, 0, 1, 0)：扫到 grid[1][0] = 1，返回 [true, true]。

bottomRight = dfs(1, 1, 1, 1)：扫到 grid[1][1] = 0，返回 [false, true]。

最终结构是：根为内部节点 [false, false]，四个孩子依次是 [false, true]、[true, true]、[true, true]、[false, true]，与期望一致。

再看一个能体现压缩的用例 grid = [[1,1],[1,1]]：dfs(0,0,1,1) 扫描四格全是 1，one = 1、zero = 0，zero + one = 1 故 isLeaf = true，val = true，直接返回单个叶节点 [true, true]，四次递归一次都没发生——这就是四叉树相对原矩阵的压缩收益。

代码实现

class Solution {
    public Node construct(int[][] grid) {
        return dfs(0, 0, grid.length - 1, grid[0].length - 1, grid);
    }

    private Node dfs(int a, int b, int c, int d, int[][] grid) {
        int zero = 0, one = 0;
        for (int i = a; i <= c; ++i) {
            for (int j = b; j <= d; ++j) {
                if (grid[i][j] == 0) {
                    zero = 1;
                } else {
                    one = 1;
                }
            }
        }
        boolean isLeaf = zero + one == 1;
        boolean val = isLeaf && one == 1;
        Node node = new Node(val, isLeaf);
        if (isLeaf) {
            return node;
        }
        node.topLeft = dfs(a, b, (a + c) / 2, (b + d) / 2, grid);
        node.topRight = dfs(a, (b + d) / 2 + 1, (a + c) / 2, d, grid);
        node.bottomLeft = dfs((a + c) / 2 + 1, b, c, (b + d) / 2, grid);
        node.bottomRight = dfs((a + c) / 2 + 1, (b + d) / 2 + 1, c, d, grid);
        return node;
    }
}

func construct(grid [][]int) *Node {
    var dfs func(a, b, c, d int) *Node
    dfs = func(a, b, c, d int) *Node {
        zero, one := 0, 0
        for i := a; i <= c; i++ {
            for j := b; j <= d; j++ {
                if grid[i][j] == 0 {
                    zero = 1
                } else {
                    one = 1
                }
            }
        }
        isLeaf := zero+one == 1
        val := isLeaf && one == 1
        node := &Node{Val: val, IsLeaf: isLeaf}
        if isLeaf {
            return node
        }
        node.TopLeft = dfs(a, b, (a+c)/2, (b+d)/2)
        node.TopRight = dfs(a, (b+d)/2+1, (a+c)/2, d)
        node.BottomLeft = dfs((a+c)/2+1, b, c, (b+d)/2)
        node.BottomRight = dfs((a+c)/2+1, (b+d)/2+1, c, d)
        return node
    }
    return dfs(0, 0, len(grid)-1, len(grid[0])-1)
}

复杂度分析

时间复杂度：$O(n^2 \log n)$。凭什么：递推式是 $T(n) = 4T(n/2) + O(n^2)$，其中 $O(n^2)$ 来自每层对区域的全量扫描。递归树共 $\log n$ 层，每一层所有节点扫描的格子总数都是 $n^2$（同一层的区域互不重叠、并集是整个矩阵），因此总量为 $n^2 \log n$。若改用二维前缀和把同质判断降到 $O(1)$，则退化为 $T(n) = 4T(n/2) + O(1)$，总量 $O(n^2)$。

空间复杂度：$O(\log n)$ 的递归栈 + $O(n^2)$ 的输出。凭什么：每次递归边长减半，栈深为 $\log n$；返回的四叉树在最坏情况（棋盘格状 01 交错，无任何可压缩区域）下有 $O(n^2)$ 个叶节点，这部分是题目要求的返回值。

关键点总结

分治题的第一件事是把递归函数的语义写成一句话。 本题是「返回以该区域为内容的四叉树根」，语义清晰之后，父节点只管挂孩子，切分与合并的责任边界就不会混。

终止条件要贴着题目的压缩语义写，而不是贴着数据规模写。 写成「区域为单格」虽然也能建出结构正确的树，但丢掉了压缩，判题不通过。

用「出现过 0 吗 / 出现过 1 吗」两个标志位代替计数，可以让同质判断变成一次加法。 这类「只关心存在性就别去计数」的化简在很多题里都能用。

闭区间切分要保证 mid 与 mid + 1 首尾相接。 四个子区域不重不漏是分治正确性的地基，写完后用 $2 \times 2$ 的最小用例逐个核对下标是最快的验证方式。

同质判断可以用二维前缀和降到 $O(1)$，把整体从 $O(n^2\log n)$ 优化到 $O(n^2)$。 区域和等于 0 说明全 0，等于面积说明全 1。

面试视角：先讲清「叶节点的含义 = 区域同质」这条压缩语义，再写四坐标的递归骨架，然后当场用 $2 \times 2$ 的例子核一遍四个子区域的下标。写完主动提前缀和优化，并说明为什么最坏情况下输出规模仍是 $O(n^2)$（棋盘格无法压缩），这说明你分清了「算法开销」与「输出规模」。

易错点总结

错误写法：终止条件写成「区域边长为 1」 → 用例 [[1,1],[1,1]]，会建出一个内部节点加四个叶节点，而期望是单个叶节点 [true, true]，判题因结构不同而失败。

错误写法：isLeaf 判成 zero + one >= 1 → 用例 [[0,1],[1,0]]，根区域两种值都有时 zero + one = 2 也被判为叶子，整棵树塌成一个节点，完全丢失矩阵信息。

错误写法：把 zero、one 当计数器累加而非置 1 → 用例 [[1,1],[1,1]]，one 累加到 4，zero + one = 4 ≠ 1，同质区域被误判为需要细分，压缩失效并产生冗余节点。

错误写法：右上区域写成 dfs(a, (b + d) / 2, (a + c) / 2, d, grid)（少了 + 1） → 用例 [[0,1],[1,0]]，右上区域变成 $[0,0] \times [0,1]$，与左上区域重叠且覆盖不到 grid[0][1] 之外，四个孩子的内容错乱。

错误写法：下半部分的行起点仍用 (a + c) / 2 而不是 (a + c) / 2 + 1 → 用例 [[0,1],[1,0]]，左下区域变成 $[0,1] \times [0,0]$，包含了本属于上半部分的行，递归无法缩小规模，最终栈溢出。

错误写法：四个孩子的挂载顺序写成左上、左下、右上、右下 → 用例 [[0,1],[1,0]]，topRight 拿到的是 grid[1][0] 的结果，形状虽同但内容错位，判题失败。

错误写法：val = one == 1 漏掉 isLeaf && → 内部节点的 val 会被置成 true；本题题面说明内部节点 val 任取皆可，所以这条在 LeetCode 上不报错，但在按值严格比较的自测框架里会误报差异，属于「依赖题目宽松判定」的隐患。

错误写法：construct 里传 grid.length 而不是 grid.length - 1 作为右下角坐标 → 用例任意矩阵，第一次扫描就访问 grid[n][*] 越界抛异常。

错误写法：为了「优化」而在发现区域非同质时提前 break 出扫描循环，却忘了此时 zero、one 的取值仍需正确 → 若 break 写在只设置了一个标志位之后，zero + one 可能仍为 1，非同质区域被误判成叶子；提前退出必须在两个标志位都置位之后。

错误写法：认为 $n$ 可能不是 2 的幂而额外处理奇数边长 → 徒增分支，且一旦切分逻辑写成「向上取整」，用例 [[0,1],[1,0]] 的子区域会出现空区间，扫描循环一次不执行导致 zero = one = 0，isLeaf 判定为 false 后无限递归。

相似题目

题目	难度	考察点
108. 将有序数组转换为二叉搜索树	简单	同为分治建树，但切分点固定取中点且不需要判断区间是否同质
240. 搜索二维矩阵 II	中等	也把矩阵按区域拆分，但目标是查找而非建树，可用行列单调性做 $O(m+n)$ 的线性剪枝
654. 最大二叉树	中等	分治的切分点由区间最大值决定而非几何中点，因此最坏情况会退化成链