Medium

题目描述

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

返回能表示矩阵的四叉树的根结点。

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

四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性：

  • val：储存叶子结点所代表的区域的值。1 对应 True，0 对应 False；
  • isLeaf：当这个节点是一个叶子结点时为 True，如果它有 4 个子节点则为 False。
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}

我们可以按以下步骤为二维区域构建四叉树：

  1. 如果当前网格的值相同（即，全为 0 或者全为 1），将 isLeaf 设为 True，将 val 设为网格相应的值，并将四个子节点都设为 Null 然后停止。
  2. 如果当前网格的值不同，将 isLeaf 设为 False， 将 val 设为任意值，然后如下图所示，将当前网格划分为四个子网格。
  3. 使用适当的子网格递归每个子节点。

示例 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

解题思路

这道题要求我们将一个二维矩阵构造成四叉树，这是一个典型的分治算法问题。

核心思路：

四叉树的构造遵循以下规则：

  1. 如果当前区域内所有值都相同，创建叶子节点，isLeaf = true，val 为该相同值
  2. 如果当前区域内的值不同，创建内部节点，isLeaf = false，然后将区域四等分，递归构造四个子节点

算法步骤：

  1. 检查统一性：遍历当前区域，判断所有值是否相同
  2. 创建叶子节点：如果值相同，直接返回叶子节点
  3. 分治处理：如果值不同，将区域分成四个子区域：
    • 左上角：[row, row+size/2) × [col, col+size/2)
    • 右上角：[row, row+size/2) × [col+size/2, col+size)
    • 左下角：[row+size/2, row+size) × [col, col+size/2)
    • 右下角：[row+size/2, row+size) × [col+size/2, col+size)
  4. 递归构造：对每个子区域递归调用构造函数

优化点：

  • 可以通过前缀和快速判断区域内值是否相同
  • 但考虑到矩阵大小限制（最大64×64），直接遍历也是可接受的

这种分治方法的时间复杂度为 O(n²log n)，空间复杂度为 O(log n)（递归栈深度）。

代码实现

class Solution {
public:
    Node* construct(vector<vector<int>>& grid) {
        return helper(grid, 0, 0, grid.size());
    }
    
private:
    Node* helper(vector<vector<int>>& grid, int row, int col, int size) {
        if (allSame(grid, row, col, size)) {
            return new Node(grid[row][col], true);
        }
        
        Node* node = new Node(true, false);
        int half = size / 2;
        node->topLeft = helper(grid, row, col, half);
        node->topRight = helper(grid, row, col + half, half);
        node->bottomLeft = helper(grid, row + half, col, half);
        node->bottomRight = helper(grid, row + half, col + half, half);
        
        return node;
    }
    
    bool allSame(vector<vector<int>>& grid, int row, int col, int size) {
        int val = grid[row][col];
        for (int i = row; i < row + size; i++) {
            for (int j = col; j < col + size; j++) {
                if (grid[i][j] != val) return false;
            }
        }
        return true;
    }
};

class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        def helper(row, col, size):
            if self.all_same(grid, row, col, size):
                return Node(grid[row][col] == 1, True)
            
            node = Node(True, False)
            half = size // 2
            node.topLeft = helper(row, col, half)
            node.topRight = helper(row, col + half, half)
            node.bottomLeft = helper(row + half, col, half)
            node.bottomRight = helper(row + half, col + half, half)
            
            return node
        
        return helper(0, 0, len(grid))
    
    def all_same(self, grid, row, col, size):
        val = grid[row][col]
        for i in range(row, row + size):
            for j in range(col, col + size):
                if grid[i][j] != val:
                    return False
        return True

public class Solution {
    public Node Construct(int[][] grid) {
        return Helper(grid, 0, 0, grid.Length);
    }
    
    private Node Helper(int[][] grid, int row, int col, int size) {
        if (AllSame(grid, row, col, size)) {
            return new Node(grid[row][col] == 1, true);
        }
        
        Node node = new Node(true, false);
        int half = size / 2;
        node.topLeft = Helper(grid, row, col, half);
        node.topRight = Helper(grid, row, col + half, half);
        node.bottomLeft = Helper(grid, row + half, col, half);
        node.bottomRight = Helper(grid, row + half, col + half, half);
        
        return node;
    }
    
    private bool AllSame(int[][] grid, int row, int col, int size) {
        int val = grid[row][col];
        for (int i = row; i < row + size; i++) {
            for (int j = col; j < col + size; j++) {
                if (grid[i][j] != val) return false;
            }
        }
        return true;
    }
}

var construct = function(grid) {
    function build(row, col, size) {
        if (size === 1) {
            return new _Node(grid[row][col] === 1, true, null, null, null, null);
        }
        
        const half = size / 2;
        const topLeft = build(row, col, half);
        const topRight = build(row, col + half, half);
        const bottomLeft = build(row + half, col, half);
        const bottomRight = build(row + half, col + half, half);
        
        if (topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf &&
            topLeft.val === topRight.val && topRight.val === bottomLeft.val && bottomLeft.val === bottomRight.val) {
            return new _Node(topLeft.val, true, null, null, null, null);
        }
        
        return new _Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
    }
    
    return build(0, 0, grid.length);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n² log n)，其中 n 是矩阵的边长。每层递归需要 O(n²) 时间检查区域统一性，总共有 O(log n) 层
空间复杂度O(log n)，递归栈的最大深度为 log n