0427. Construct Quad Tree ========================= 题目信息 -------- :题号: 0427 :难度: Medium :主题: 二值方阵、四叉树、均匀区域、递归划分 :原题: `LeetCode 0427 `_ :重点: 均匀区域生成叶节点、混合区域平均分成四块、叶节点没有子节点、非叶节点的 ``val`` 不参与判定 题目重述 -------- 给定只包含 0 和 1 的 ``n × n`` 方阵 ``grid``,构造表示该矩阵的四叉树。若当前正方形区域中的所有值都相同,则创建叶节点,``isLeaf`` 为 ``true``,``val`` 等于该区域的布尔值,四个子节点均为空。 若区域同时包含 0 和 1,则创建非叶节点,并把区域等分为左上、右上、左下、右下四个同样大小的正方形,分别递归构造四个子树。非叶节点的 ``val`` 可以为任意布尔值,判题时会忽略它。 ``n`` 位于 ``[1, 64]`` 且是 2 的幂,矩阵元素只能是 0 或 1。返回四叉树根节点。 自建示例 -------- 整个矩阵均匀: .. code-block:: text 输入:grid = [[1,1],[1,1]] 输出:一个 isLeaf = true、val = true 的根节点 解释:整个区域都是 1,无需继续划分,根节点的四个子节点均为空。 四个象限取值不同: .. code-block:: text 输入:grid = [[1,0],[0,1]] 输出:一个非叶根节点,四个叶子依次表示左上 1、右上 0、左下 0、右下 1 解释:根区域并不均匀,因此必须划分成四个 1×1 区域,每个区域单独成为叶节点。 先判断区域是否均匀,再递归四等分 ---------------------------------- 对当前正方形扫描一次,若所有值都等于左上角值,就可以直接创建叶节点;只有发现 0 和 1 混合时才把区域按中线分成四个象限。四个象限的顺序固定为左上、右上、左下、右下,分别递归后挂到非叶节点上。 ``n`` 是 2 的幂,因此不断二分最终会到达单元格;单元格天然均匀,不需要额外的停止条件。非叶节点的 ``val`` 不参与表达区域值,设为任意合法布尔值即可。 C++ 实现 -------- .. code-block:: cpp class Solution { Node* build(std::vector>& grid, int row, int col, int size) { int value = grid[row][col]; bool uniform = true; for (int r = row; r < row + size && uniform; ++r) { for (int c = col; c < col + size; ++c) { if (grid[r][c] != value) { uniform = false; break; } } } if (uniform) return new Node(value == 1, true); int half = size / 2; Node* node = new Node(true, false); node->topLeft = build(grid, row, col, half); node->topRight = build(grid, row, col + half, half); node->bottomLeft = build(grid, row + half, col, half); node->bottomRight = build( grid, row + half, col + half, half); return node; } public: Node* construct(std::vector>& grid) { return build(grid, 0, 0, static_cast(grid.size())); } }; 代码分析 -------- 每个区域只有在确实混合时才继续分割,叶节点的四个子指针保持为空;递归覆盖且不重叠地覆盖整个矩阵,因此树能还原每个格子的值。朴素扫描的最坏时间复杂度为 ``O(n^2 log n)``,递归树额外空间为 ``O(log n)``(不计输出节点)。