427 建立四叉树

题目描述#

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

四叉树每个节点有两个属性：

val：叶子节点所代表区域的值（1 对应 True，0 对应 False）；非叶子节点的 val 任意。
isLeaf：当前节点是叶子时为 True，否则为 False。

构建规则：

如果当前子网格全部相同（全 0 或全 1），就建一个叶子节点，isLeaf = true，val 设为相应值。
否则把网格平均切成 4 块，对每一块递归建子树。

思路#

咔嚓——一张照片切四块，照样能拼回原图哦～

四叉树长得就像把一张照片对半折两次：每次切成四宫格，纯色的格子直接当叶子收工，杂色的就接着切。这种"先看整块、不行就裁四块"的姿势，简直就是分治本治！

具体写法用 (r0, c0, r1, c1) 这两对坐标圈出当前区域，递归函数 dfs 干两件事：

检查这块是否纯色：扫一遍区域，只要发现有任何一格和左上角 grid[r0][c0] 不一样，就说明这块花啦，需要继续裁。
裁就裁四份：算出行中线 rmid 和列中线 cmid，分别 dfs 左上、右上、左下、右下四个象限作为子节点。
纯色就建叶子：扫完没发现异色，就直接返回 Node{Val: grid[r0][c0] == 1, IsLeaf: true}，四个子指针留 nil。

代码里有个很赞的小手筋——把"扫描判断"和"递归裁分"写在了同一个双重循环里：一旦扫到第一个不同元素，立刻就地返回带四个子节点的内部节点；扫完整块都没有差异，循环结束才落地建叶子。这样不用先扫一遍再判断、然后再扫一遍裁分，只走一遍数据搞定，挺优雅的～

思维边界#

中线公式必须用 r0 + (r1-r0)/2 这种形式，不能写 (r0+r1)/2——题目数据虽然小，但养成习惯避免大数溢出，本姑娘可不想看到 OJ 飘红。
子区间的边界采用左闭右开 [r0, r1) × [c0, c1)，所以四个子调用里 rmid、cmid 既当上半的右端、又当下半的左端，绝对不会漏行也不会重格。
内部节点的 Val 是任意的——题解里写 true 只是图省事，写 false 判题机也接受。val 真正起作用的只有叶子节点。
扫描判断的复杂度：每层扫 O(n²)，递归 log n 层，总复杂度 O(n² log n)。如果想优化到 O(n²) 可以用二维前缀和提前判断"区域是否纯色"，但本题规模够小，朴素写法足矣。
不要忘了 n == 1 的边界——递归会立刻命中"纯色"分支返回叶子，不会爆栈～

分治三连：切一刀、再切一刀、合个影～

代码#

/**
 * Definition for a QuadTree node.
 * type Node struct {
 *     Val bool
 *     IsLeaf bool
 *     TopLeft *Node
 *     TopRight *Node
 *     BottomLeft *Node
 *     BottomRight *Node
 * }
 */

func construct(grid [][]int) *Node {
    n := len(grid)
    var dfs func(r0, c0, r1, c1 int) *Node
    // r为行 c为列
    dfs = func(r0, c0, r1, c1 int) *Node {
        for i := r0; i < r1; i++ {
            for j := c0; j < c1; j++ {
                if grid[i][j] != grid[r0][c0] {
                    rmid := r0 + (r1-r0)/2
                    cmid := c0 + (c1-c0)/2
                    return &Node{
                        Val:         true,
                        IsLeaf:      false,
                        TopLeft:     dfs(r0, c0, rmid, cmid),
                        TopRight:    dfs(r0, cmid, rmid, c1),
                        BottomLeft:  dfs(rmid, c0, r1, cmid),
                        BottomRight: dfs(rmid, cmid, r1, c1),
                    }
                }
            }
        }
        return &Node{
            Val:    grid[r0][c0] == 1,
            IsLeaf: true,
        }
    }
    return dfs(0, 0, n, n)
}