Untitled

/*
// 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() {
        this.val = false;
        this.isLeaf = false;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
}
*/

class Solution {
    public static Node construct(int[][] grid) {
        int n = grid.length;

        return construct(grid, 0, 0, n - 1, n - 1);
    }

    private static Node construct(int[][] grid, int x1,  int y1, int x2, int y2) {

        if (x1 < 0 || x1 >= grid.length || x2 < 0 || x2 >= grid.length || y1 < 0 || y1 >= grid.length || y2 < 0 || y2 >= grid.length || x1 > x2 || y1 > y2) {
            return null;
        }

        if (x1 == x2 && y1 == y2) {
            boolean flag = grid[x1][y1] == 1 ? true : false;
            return new Node(flag, true);
        }

        int newX2 = x1 + (x2 - x1)/2;
        int newY2 = y1 + (y2 - y1)/2;

        //System.out.println("Top left going to (" + x1 + " - " + y1 + " " + newX2 + " - " + newY2 + ") ");

        Node topLeft = construct(grid, x1, y1, newX2 , newY2);

        int newY1 = y1 + (y2 - y1)/2 + 1;
        newX2 = x1 + (x2 - x1)/2;
       // System.out.println("Top right going to (" + x1 + " - " + newY1 + " " + newX2 + " - " + y2 + ") ");
        Node topRight = construct(grid, x1, newY1, newX2, y2);

        int newX1 = x1 + (x2 - x1)/2 + 1;
        newY2 = y1 + (y2 - y1)/2;
       // System.out.println("Bottom left going to (" + newX1 + " - " + y1 + " " + x2 + " - " + newY2 + ") ");
        Node bottomLeft = construct(grid, newX1, y1, x2, newY2);

        newX1 = x1 + (x2 - x1)/2 + 1;
        newY1 = y1 + (y2 - y1)/2 + 1;

      //  System.out.println("Bottom right going to (" + newX1 + " - " + newY1 + " " + x2 + " - " + y2 + ") ");
        Node bottomRight = construct(grid, newX1, newY1, x2, y2);



        if (topLeft == null && topRight == null && bottomLeft == null && bottomRight == null) {
            boolean flag = grid[x1][y1] == 1 ? true : false;
            return new Node(flag, true);
        }


        if (topLeft.val == topRight.val  && topRight.val == bottomLeft.val  && bottomLeft.val == bottomRight.val) {
            return new Node(topLeft.val, true);
        }

        return new Node(topLeft.val, false, topLeft, topRight, bottomLeft, bottomRight);

    }
}