給定一個 n x n 的二維矩陣（值為 0 或 1），建構對應的四元樹 (Quad Tree)。如果一個區域內所有值相同，該區域就是一個葉子節點；否則將區域分成四等份，遞迴建構。
Example:
Input: grid = [[0,1],[1,0]] Output: [[0,1],[1,0],[1,1],[1,1],[1,0]] (四元樹的序列化表示)
Intuition
TIP
遞迴分治：檢查區域是否所有值相同，相同則為葉子，不同則分成四塊遞迴。
- 四元樹將二維空間分成四個象限：左上、右上、左下、右下
- 如果當前區域所有值相同，建立葉子節點
- 否則分成四個子區域遞迴建構
Approaches
⭐ 1. Recursive Divide & Conquer — O(n^2 log n) / O(log n)
- Idea: 檢查區域一致性，不一致則分成四等份遞迴
- Time:
O(n^2 log n)，每層遞迴需要檢查區域內所有元素 - Space:
O(log n)，遞迴深度
class Solution {
fun construct(grid: Array<IntArray>): Node? {
return build(grid, 0, 0, grid.size)
}
private fun build(grid: Array<IntArray>, row: Int, col: Int, size: Int): Node {
if (isUniform(grid, row, col, size)) {
return Node(grid[row][col] == 1, true)
}
val half = size / 2
val topLeft = build(grid, row, col, half)
val topRight = build(grid, row, col + half, half)
val bottomLeft = build(grid, row + half, col, half)
val bottomRight = build(grid, row + half, col + half, half)
return Node(false, false).apply {
this.topLeft = topLeft
this.topRight = topRight
this.bottomLeft = bottomLeft
this.bottomRight = bottomRight
}
}
private fun isUniform(grid: Array<IntArray>, row: Int, col: Int, size: Int): Boolean {
val value = grid[row][col]
for (i in row until row + size) {
for (j in col until col + size) {
if (grid[i][j] != value) return false
}
}
return true
}
}2. Recursive Divide & Conquer (Prefix-Sum) — O(n^2) / O(n^2)
- Idea: 用前綴和陣列預處理，O(1) 判斷區域是否一致
- Time:
O(n^2)，前綴和預處理 O(n^2)，每個節點建構 O(1) - Space:
O(n^2)，前綴和陣列
class Solution {
private lateinit var prefixSum: Array<IntArray>
fun construct(grid: Array<IntArray>): Node? {
val n = grid.size
prefixSum = Array(n + 1) { IntArray(n + 1) }
for (i in 1..n) {
for (j in 1..n) {
prefixSum[i][j] = grid[i - 1][j - 1] +
prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1]
}
}
return build(grid, 0, 0, n)
}
private fun build(grid: Array<IntArray>, row: Int, col: Int, size: Int): Node {
val total = getSum(row, col, size)
if (total == 0) return Node(false, true)
if (total == size * size) return Node(true, true)
val half = size / 2
return Node(false, false).apply {
topLeft = build(grid, row, col, half)
topRight = build(grid, row, col + half, half)
bottomLeft = build(grid, row + half, col, half)
bottomRight = build(grid, row + half, col + half, half)
}
}
private fun getSum(row: Int, col: Int, size: Int): Int {
val r2 = row + size
val c2 = col + size
return prefixSum[r2][c2] - prefixSum[row][c2] - prefixSum[r2][col] + prefixSum[row][col]
}
}🔑 Takeaways
- Pattern: 分治法 — 將二維區域遞迴分成四個子區域
- Key trick: 前綴和可以將「判斷區域是否一致」的時間從 O(size^2) 降到 O(1)