LeetCode 427. 建立四叉树

Categories:

题目描述
思路分析
1. 解法一：递归分治（推荐）
相似题目

题目描述

✅ 427. 建立四叉树

思路分析

解法一：递归分治（推荐）

核心思路：

若当前子矩阵元素全相同，则生成叶子节点。

否则将矩阵划分为四块，递归构建四个子树。

内部节点 isLeaf=false，并持有四个子节点。

复杂度分析：

时间复杂度：O(n^2 log n)，其中 n 为矩阵边长。

空间复杂度：O(log n)，递归栈深度。

class Solution {
    public Node construct(int[][] grid) {
        int n = grid.length;
        return build(grid, 0, 0, n);
    }

    private Node build(int[][] grid, int r, int c, int size) {
        if (isSame(grid, r, c, size)) {
            return new Node(grid[r][c] == 1, true);
        }

        int half = size / 2;
        Node topLeft = build(grid, r, c, half);
        Node topRight = build(grid, r, c + half, half);
        Node bottomLeft = build(grid, r + half, c, half);
        Node bottomRight = build(grid, r + half, c + half, half);

        return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
    }

    private boolean isSame(int[][] grid, int r, int c, int size) {
        int val = grid[r][c];
        for (int i = r; i < r + size; i++) {
            for (int j = c; j < c + size; j++) {
                if (grid[i][j] != val) {
                    return false;
                }
            }
        }
        return true;
    }
}

func construct(grid [][]int) *Node {
    n := len(grid)
    return buildQuad(grid, 0, 0, n)
}

func buildQuad(grid [][]int, r int, c int, size int) *Node {
    if isSame(grid, r, c, size) {
        return &Node{Val: grid[r][c] == 1, IsLeaf: true}
    }

    half := size / 2
    topLeft := buildQuad(grid, r, c, half)
    topRight := buildQuad(grid, r, c+half, half)
    bottomLeft := buildQuad(grid, r+half, c, half)
    bottomRight := buildQuad(grid, r+half, c+half, half)

    return &Node{
        Val:         false,
        IsLeaf:      false,
        TopLeft:     topLeft,
        TopRight:    topRight,
        BottomLeft:  bottomLeft,
        BottomRight: bottomRight,
    }
}

func isSame(grid [][]int, r int, c int, size int) bool {
    val := grid[r][c]
    for i := r; i < r+size; i++ {
        for j := c; j < c+size; j++ {
            if grid[i][j] != val {
                return false
            }
        }
    }
    return true
}

相似题目

题目	难度	考察点
200. 岛屿数量	中等	DFS
695. 岛屿的最大面积	中等	DFS
558. 四叉树交集	中等	分治
102. 二叉树的层序遍历	中等	递归构造
889. 根据前序和后序遍历构造二叉树	中等	递归

本文作者: HGNULB

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