LeetCode 427. 建立四叉树

2026-03-28 HGNULB 约 5 分钟

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

分类

LeetCode 中等 面试经典 150 题

标签

数组 树 矩阵 分治

题目描述

✅ 427. 建立四叉树

题意分析

将由 0、1 组成的正方形网格表示成四叉树。一块区域如果所有格子取值相同，就用一个叶子节点表示它；如果内部混合两种值，就分成左上、右上、左下、右下四块继续描述。

叶子的 val 表示这一整块是零还是一，isLeaf 为真，四个孩子为空。内部节点的实际内容由四个孩子决定，val 本身可以任选布尔值。题目给定的边长是 2 的幂，能够不断等分直到单格。

解法：按同质区域递归四分

核心思路

[!blue]

定义 dfs(a, b, c, d) 返回行范围 [a, c]、列范围 [b, d] 这块闭区间区域对应的四叉树节点。根调用覆盖整个网格，递归只负责当前区域，不需要复制子矩阵。

扫描当前区域，用 zero、one 两个标记分别表示是否出现过零和一。它们是存在标记而非格子数量：只出现一种值时，整个区域同质，直接创建叶子；两种都出现时，必须创建内部节点并继续分割。

对混合区域，分别取行中点和列中点，形成四个互不重叠的子区域。左半与上半包含中点，右半与下半从中点加一开始，四块恰好覆盖原区域；分别递归后，按左上、右上、左下、右下挂到对应孩子字段。

每个子调用都正确表示自己的那一块，四个孩子合起来就完整表示父区域；同质区域则被一个叶子直接压缩。边长每次减半，单格必然同质，因此递归最终一定终止。

代码对内部节点统一使用 false 作为 val，这不表示区域全为零；判断是否可以这样解读，必须先看 isLeaf。

解题步骤

1. 从整个网格的闭区间调用递归。
2. 扫描区域，分别标记是否出现零和一。
3. 只有一种值时创建并返回叶子，叶值由该区域实际值决定。
4. 两种值都有时创建内部节点，按行列中点划出四个子区域。
5. 依固定方向递归并连接四个孩子，返回构造好的当前节点。

代码实现

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;
        int 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)
}

复杂度分析

设网格边长为 n。

• 时间复杂度：最坏 $O(n^2\log(n+1))$。每层各区域互不重叠，总计最多扫描 $n^2$ 个格子，分割层数与 $\log n$ 同阶；若整块同质，扫描一次就结束。
• 空间复杂度：除输出树外为 $O(\log(n+1))$ 的递归栈。完全分到单格时，输出树本身最多占 $O(n^2)$ 空间。

关键点总结

[!green]

• 每个递归状态明确对应一个网格区域，返回节点完整表示该区域。
• 同质性决定是否停在叶子，四分决定混合区域如何继续表达。
• 闭区间的中点归属要统一，保证四个孩子不重不漏且方向固定。

易错点总结

[!yellow]

• 只根据某一个格子的值就判叶子，无法确认其他位置是否相同，必须判断整个区域。
• 全相同区域仍继续拆分，会失去应有的叶子压缩，也不符合本题的构造规则。
• 右半或下半也从中点开始，会重复包含中间行列；应从中点加一开始。
• 四个孩子字段顺序交换，会把正确子区域放到错误方向，表示的网格也随之改变。
• 根据内部节点 val 判断整块颜色，忽略了只有叶子的值才承担同质区域含义。

相似题目

题目	难度	关联与区别
304. 二维区域和检索 - 矩阵不可变	中等	二维前缀和可用区域和是否为 0 或面积来判断同质，将重复扫描优化为常数时间查询。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/35940830

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！