LeetCode 第427题：建立四叉树

📖 文章摘要

本文详细解析LeetCode第427题“建立四叉树”，这是一道考察四叉树构建和矩阵分治的问题。文章提供了基于递归和分治的解题思路，包含C#、Python、C++三种语言实现，配有详细的分析和性能对比。适合想要提升分治算法和树结构操作能力的程序员。

核心知识点： 四叉树、分治算法、矩阵操作 难度等级： 中等 推荐人群： 具有基础数据结构知识的程序员

题目描述

给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。

四叉树是一种树数据结构，其中每个结点都有四个子结点。此外，每个结点都有两个属性：

val：储存叶子结点所代表的区域的值。1 对应 True，0 对应 False；
isLeaf：当这个节点是叶子结点时为 True，如果它有 4 个子节点则为 False 。

注意，当 isLeaf 为 False 时，你可以把 True 或者 False 赋值给节点，两种值都会被判题系统接受。

示例

示例 1：

输入：grid = [[0,1],[1,0]]
输出：[[0,1],[1,0],[1,1],[1,1],[1,0]]
解释：此示例的解释如下：
请注意，在下面四叉树的图示中，0 表示 false，1 表示 True 。

示例 2：

输入：grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
输出：[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]

提示

n == grid.length == grid[i].length
n == 2^x，其中 0 <= x <= 6
grid[i][j] 不是 0 就是 1

解题思路

本题可以使用分治法来解决，主要步骤如下：

检查当前区域是否为叶子节点：
- 如果区域内所有值相同，创建叶子节点
- 否则需要继续分割
分割区域：
- 将当前区域分成四个相等的子区域
- 递归处理每个子区域
合并结果：
- 创建内部节点
- 连接四个子节点

图解思路

四叉树构建过程

步骤	操作	结果	说明
初始状态	-	原始矩阵	n×n的二进制矩阵
区域检查	判断是否同值	叶子/内部节点	决定是否需要分割
分割处理	划分四个子区域	子树构建	递归处理子区域
节点合并	连接子节点	完整四叉树	构建树结构

区域分割示意

位置	坐标范围	子树位置	说明
左上	(x,y) 到 (x+n/2,y+n/2)	topLeft	第一象限
右上	(x,y+n/2) 到 (x+n/2,y+n)	topRight	第二象限
左下	(x+n/2,y) 到 (x+n,y+n/2)	bottomLeft	第三象限
右下	(x+n/2,y+n/2) 到 (x+n,y+n)	bottomRight	第四象限

代码实现

C# 实现

public class Solution {
    public Node Construct(int[][] grid) {
        return BuildQuadTree(grid, 0, 0, grid.Length);
    }
  
    private Node BuildQuadTree(int[][] grid, int x, int y, int n) {
        // 检查当前区域是否为叶子节点
        if (IsLeaf(grid, x, y, n)) {
            return new Node(grid[x][y] == 1, true);
        }
      
        // 创建非叶子节点
        Node node = new Node(true, false);
        n = n / 2;
      
        // 递归构建四个子节点
        node.topLeft = BuildQuadTree(grid, x, y, n);
        node.topRight = BuildQuadTree(grid, x, y + n, n);
        node.bottomLeft = BuildQuadTree(grid, x + n, y, n);
        node.bottomRight = BuildQuadTree(grid, x + n, y + n, n);
      
        return node;
    }
  
    private bool IsLeaf(int[][] grid, int x, int y, int n) {
        int value = grid[x][y];
        for (int i = x; i < x + n; i++) {
            for (int j = y; j < y + n; j++) {
                if (grid[i][j] != value) {
                    return false;
                }
            }
        }
        return true;
    }
}

Python 实现

class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        def is_leaf(x: int, y: int, n: int) -> bool:
            # 检查当前区域是否为叶子节点
            value = grid[x][y]
            for i in range(x, x + n):
                for j in range(y, y + n):
                    if grid[i][j] != value:
                        return False
            return True
      
        def build_quad_tree(x: int, y: int, n: int) -> 'Node':
            if is_leaf(x, y, n):
                return Node(grid[x][y] == 1, True)
          
            # 创建非叶子节点
            node = Node(True, False)
            n = n // 2
          
            # 递归构建四个子节点
            node.topLeft = build_quad_tree(x, y, n)
            node.topRight = build_quad_tree(x, y + n, n)
            node.bottomLeft = build_quad_tree(x + n, y, n)
            node.bottomRight = build_quad_tree(x + n, y + n, n)
          
            return node
      
        return build_quad_tree(0, 0, len(grid))

C++ 实现

class Solution {
public:
    Node* construct(vector<vector<int>>& grid) {
        return buildQuadTree(grid, 0, 0, grid.size());
    }
  
private:
    bool isLeaf(vector<vector<int>>& grid, int x, int y, int n) {
        int value = grid[x][y];
        for (int i = x; i < x + n; i++) {
            for (int j = y; j < y + n; j++) {
                if (grid[i][j] != value) {
                    return false;
                }
            }
        }
        return true;
    }
  
    Node* buildQuadTree(vector<vector<int>>& grid, int x, int y, int n) {
        if (isLeaf(grid, x, y, n)) {
            return new Node(grid[x][y], true);
        }
      
        Node* node = new Node(true, false);
        n = n / 2;
      
        node->topLeft = buildQuadTree(grid, x, y, n);
        node->topRight = buildQuadTree(grid, x, y + n, n);
        node->bottomLeft = buildQuadTree(grid, x + n, y, n);
        node->bottomRight = buildQuadTree(grid, x + n, y + n, n);
      
        return node;
    }
};

执行结果

C# 实现

执行用时：88 ms
内存消耗：38.2 MB

Python 实现

执行用时：76 ms
内存消耗：15.8 MB

C++ 实现

执行用时：12 ms
内存消耗：16.2 MB

性能对比

语言	执行用时	内存消耗	特点
C#	88 ms	38.2 MB	实现清晰但性能较差
Python	76 ms	15.8 MB	代码简洁，性能中等
C++	12 ms	16.2 MB	性能最优

代码亮点

🎯 使用分治法优化递归过程
💡 巧妙处理区域划分
🔍 高效的叶子节点判断
🎨 代码结构清晰，易于维护

常见错误分析

🚫 区域划分计算错误
🚫 忘记检查叶子节点条件
🚫 子节点连接顺序错误
🚫 边界条件处理不当

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
递归分治	O(n²)	O(log n)	实现简单，直观	重复遍历部分区域
预处理优化	O(n²)	O(n²)	避免重复遍历	需要额外空间

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第427题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

图解思路

四叉树构建过程

区域分割示意

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流