题目要求

理解

哦题目好长……

把矩阵递归四分，直到每个小块内的值相同（为叶子节点）；
叶子节点 $i s L e a f = 1$ ， $v a l$ 设为小块内的值（块内每个格子值相等）；
非叶子节点 $i s L e a f = 0$ ， $v a l$ 随便。

思路一：递归

递归判断当前矩阵范围内值是否都相等
- 相等则为叶子，返回(值, true)
- 不相等则从中间划分为四个，分别再判断
可以直接用左上角点 $(t l x, t l y)$ 和右下角点 $(b r x, b r y)$ 的坐标来划定矩阵范围
- 划分时分别砍半横着 $\frac{tlx+brx}{2}$ 、竖着 $\frac{tly+bry}{2}$

Java

class Solution {
    int[][] g;
    public Node construct(int[][] grid) {
        g = grid;
        int n = g.length;
        return DFS(0, 0, n, n);
    }

    Node DFS(int tlx, int tly, int brx, int bry) {
        boolean equ = true;
        int t = g[tlx][tly];
        // 块内所有值相等
        for(int i = tlx; i < brx && equ; ++i)
            for(int j = tly; j < bry && equ; ++j)
                if(g[i][j] != t)
                    equ = false;
        if(equ)
            return new Node(t == 1, true); // 叶子

        int nx = (brx + tlx) / 2, ny = (bry + tly) / 2; // 分割线
        Node root = new Node(
            true,
            false,
            DFS(tlx, tly, nx, ny),
            DFS(tlx, ny, nx, bry),
            DFS(nx, tly, brx, ny),
            DFS(nx, ny, brx, bry)
        );
              
        return root;
    }
}

时间复杂度： $O(n^2+n^2\times\log n)$ ，单次递归调用4个子递归，其规模为 $\frac{n}{2}\times\frac{n}{2}$ ，复杂度共 $4O(\frac{n^2}{4})=O(n^2)$ ；判断块内所有值相等复杂度为 $O(n^2)$ ，最多拆分 $\log n$ 次（也是需判断次数），所以递归内复杂度为 $O(n^2\times\log n)$
空间复杂度： $O (1)$ ，忽略递归的额外空间开销

C++

class Solution {
    vector<vector<int>> g;
public:
    Node* construct(vector<vector<int>>& grid) {
        g = grid;
        int n = g.size();
        return DFS(0, 0, n, n);
    }

    Node* DFS(int tlx, int tly, int brx, int bry) {
        bool equ = true;
        int t = g[tlx][tly];
        // 块内所有值相等
        for(int i = tlx; i < brx && equ; ++i)
            for(int j = tly; j < bry && equ; ++j)
                if(g[i][j] != t)
                    equ = false;
        if(equ)
            return new Node(t == 1, true); // 叶子

        int nx = (brx + tlx) / 2, ny = (bry + tly) / 2; // 分割线
        Node* root = new Node(
            true,
            false,
            DFS(tlx, tly, nx, ny),
            DFS(tlx, ny, nx, bry),
            DFS(nx, tly, brx, ny),
            DFS(nx, ny, brx, bry)
        );
              
        return root;
    }
};

时间复杂度： $O(n^2+n^2\times\log n)$ ，单次递归调用4个子递归，其规模为 $\frac{n}{2}\times\frac{n}{2}$ ，复杂度共 $O(n^2)$ ；判断块内所有值相等复杂度为 $O(n^2)$ ，最多拆分 $\log n$ 次（也是需判断次数），所以递归内复杂度为 $O(n^2\times\log n)$
空间复杂度： $O (1)$ ，忽略递归的额外空间开销

思路二：递归+前缀和

前面判断块内所有值相等的暴力方法可以采用前缀和优化
记录内容其实为每一部分的面积，为 $0$ 或为 $当前块内格子数$ 则相同（为叶子），否则划分判断

Java

class Solution {
    int[][] g;
    int[][] pre = new int[70][70];
    public Node construct(int[][] grid) {
        g = grid;
        int n = g.length;
        // 前缀和
        for(int i = 1; i <= n; ++i) 
            for(int j = 1; j <= n; ++j)
                pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + grid[i - 1][j - 1];

        return DFS(0, 0, n, n);
    }

    Node DFS(int tlx, int tly, int brx, int bry) {
        int tot = pre[brx][bry] - pre[brx][tly] - pre[tlx][bry] + pre[tlx][tly];
        // 叶子
        if(tot == 0)
            return new Node(false, true);
        else if(tot == (brx - tlx) * (bry - tly))
            return new Node(true, true);
       
        int nx = (tlx + brx) / 2, ny = (tly + bry) / 2; // 分割线
        Node root = new Node(
            true,
            false,
            DFS(tlx, tly, nx, ny),
            DFS(tlx, ny, nx, bry),
            DFS(nx, tly, brx, ny),
            DFS(nx, ny, brx, bry)
        );
        return root;
    }
}

时间复杂度： $O(n^2+\log n)$ ，递归复杂度和上面一样为 $O(n^2)$ ，二维前缀和预处理复杂度也为 $O(n^2)$ ；递归内判断复杂度O(1)，拆分O(log n)次【这部分是基于上一方法思路的个人胡乱分析，其实小于前面部分可以拿掉写成 $O(n^2)$ 】
空间复杂度： $O(n^2)$ ，二维前缀和所需

C++

class Solution {
private:
    vector<vector<int>> g;
    vector<vector<int>> pre = vector<vector<int>> (70, vector<int>(70, 0));
public:
    Node* construct(vector<vector<int>>& grid) {
        g = grid;
        int n = g.size();
        // 前缀和
        for(int i = 1; i <= n; ++i) 
            for(int j = 1; j <= n; ++j)
                pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + grid[i - 1][j - 1];

        return DFS(0, 0, n, n);
    }

    Node* DFS(int tlx, int tly, int brx, int bry) {
        int tot = pre[brx][bry] - pre[brx][tly] - pre[tlx][bry] + pre[tlx][tly];
        // 叶子
        if(tot == 0)
            return new Node(false, true);
        else if(tot == (brx - tlx) * (bry - tly))
            return new Node(true, true);

        int nx = (brx + tlx) / 2, ny = (bry + tly) / 2; // 分割线
        Node* root = new Node(
            true,
            false,
            DFS(tlx, tly, nx, ny),
            DFS(tlx, ny, nx, bry),
            DFS(nx, tly, brx, ny),
            DFS(nx, ny, brx, bry)
        );
              
        return root;
    }
};

时间复杂度： $O(n^2+\log n)$ ，递归复杂度和上面一样为 $O(n^2)$ ，二维前缀和预处理复杂度也为 $O(n^2)$ ；递归内判断复杂度为O(1)，拆分O(\log n)$次【这部分是基于上一方法思路的个人胡乱分析，其实小于前面部分可以拿掉写成 $O(n^2)$ 】
空间复杂度： $O(n^2)$ ，二维前缀和所需

二维`vector`初始化

学习参考链接
格式为vector<vector<int>> vec(n, vector<int>(m, 0));， $n$ 为容器大小， $m$ 为容器内每个值大小。
但是直接初始化全局变量会报错：

expected parameter declarator
- 意为编译器无法区分该语句是在声明变量还是函数，所以可以类比java的初始化方法，即
```
vector<vector<int>> vec = vector<vector<int>> (n, vector<int>(m, 0));
```
- 其他解决方案参考这里