We want to use quad trees to store anN x Nboolean grid. Each cell in the grid can only be true or false. The root node represents the whole grid. For each node, it will be subdivided into four children nodesuntil the values in the region it represents are all the same.

Each node has another two boolean attributes :isLeafandval.isLeafis true if and only if the node is a leaf node. Thevalattribute for a leaf node contains the value of the region it represents.

递归，按照要求做

/*
// Definition for a QuadTree node.
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    public Node() {}

    public Node(boolean _val,boolean _isLeaf,Node _topLeft,Node _topRight,Node _bottomLeft,Node _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};
*/
class Solution {
    public Node construct(int[][] grid) {
        if(grid == null || grid.length == 0)
            return null;

        return construct(grid, 0, 0, grid.length - 1, grid.length - 1);
    }

    public Node construct(int[][] grid, int minRow, int minCol, int maxRow, int maxCol) {
        if(minRow > maxRow || minCol > maxCol)
            return null;


        if(same(grid, minRow, minCol, maxRow, maxCol))
            return new Node(grid[minRow][minCol] == 1, true, null, null, null, null);

        int midRow = minRow + (maxRow - minRow) / 2;
        int midCol = minCol + (maxCol - minCol) / 2;

        Node n1 = construct(grid, minRow, minCol, midRow, midCol);
        Node n2 = construct(grid, minRow, midCol + 1, midRow, maxCol);
        Node n3 = construct(grid, midRow + 1, minCol, maxRow, midCol);
        Node n4 = construct(grid, midRow + 1, midCol + 1, maxRow, maxCol);

        Node root = new Node(false, false);
        root.topLeft = n1;
        root.topRight = n2;
        root.bottomLeft = n3;
        root.bottomRight = n4;

        return root;
    }

    public boolean same(int[][] grid, int minRow, int minCol, int maxRow, int maxCol) {
        int num = grid[minRow][minCol];

        for(int i = minRow; i <= maxRow; i++) {
            for(int j = minCol; j <= maxCol; j++) {
                if(grid[i][j] != num)
                    return false;
            }
        }

        return true;
    }
}