/*
// 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) {
        return construct(grid, 0, 0, grid.length);
    }

    private Node construct(int[][] grid, int x, int y, int n) {
        if (n == 1)
            return new Node(grid[y][x] == 1, true, null, null, null, null);
        n /= 2;
        Node tl = construct(grid, x, y, n);
        Node tr = construct(grid, x + n, y, n);
        Node bl = construct(grid, x, y + n, n);
        Node br = construct(grid, x + n, y + n, n);
        if (tl.isLeaf && tr.isLeaf && bl.isLeaf && br.isLeaf && tl.val == tr.val && tr.val == bl.val && bl.val == br.val)
            return new Node(tl.val, true, null, null, null, null);
        return new Node(true, false, tl, tr, bl, br);
    }
}