427. Construct Quad Tree

Medium

Description

給定一個 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#

遞迴分治：檢查區域是否所有值相同，相同則為葉子，不同則分成四塊遞迴。

四元樹將二維空間分成四個象限：左上、右上、左下、右下
如果當前區域所有值相同，建立葉子節點
否則分成四個子區域遞迴建構

Approaches#

⭐ 1: 遞迴分治#

概念: 檢查區域一致性，不一致則分成四等份遞迴
時間複雜度: O(n^2 log n)，每層遞迴需要檢查區域內所有元素
空間複雜度: 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: 遞迴分治 (前綴和優化)#

概念: 用前綴和陣列預處理，O(1) 判斷區域是否一致
時間複雜度: O(n^2)，前綴和預處理 O(n^2)，每個節點建構 O(1)
空間複雜度: 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: 分治法 — 將二維區域遞迴分成四個子區域
關鍵技巧: 前綴和可以將「判斷區域是否一致」的時間從 O(size^2) 降到 O(1)