Untitled

 avatar
unknown
java
9 months ago
2.4 kB
5
Indexable
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) {
            System.out.println("Match at " + x1 + " - " + y1 + " - value " + grid[x1][y1]);
            return new Node(grid[x1][y1] == 1, true);
        }

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

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

        int newY1 = y1 + (y2 - y1)/2 + 1;
        newX2 = x1 + (x2 - x1)/2;
        Node topRight = construct(grid, x1, newY1, newX2, y2);

        int newX1 = x1 + (x2 - x1)/2 + 1;
        newY2 = y1 + (y2 - y1)/2;
        Node bottomLeft = construct(grid, newX1, y1, x2, newY2);

        newX1 = x1 + (x2 - x1)/2 + 1;
        newY1 = y1 + (y2 - y1)/2 + 1;
        
        Node bottomRight = construct(grid, newX1, newY1, x2, y2);



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

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

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

    }

    public static void main(String[] args) {
        int grid[][] = {{1,1,0,0},{1,1,0,0},{0,0,1,1},{0,0,1,1}};

        Node node = construct(grid);

        System.out.println(node.isLeaf + " - " + node.val);
        System.out.println("Top Left " + node.topLeft.isLeaf + " - " + node.topLeft.val);
        System.out.println("Top Right " + node.topRight.isLeaf + " - " + node.topRight.val);
        System.out.println("Bottom Left " + node.bottomLeft.isLeaf + " - " + node.bottomLeft.val);
        System.out.println("Bottom Right " + node.bottomRight.isLeaf + " - " + node.bottomRight.val);



        System.out.println("Top Left " + node.topLeft.topLeft.isLeaf + " - " + node.topLeft.topLeft.val);
    }
}
Editor is loading...
Leave a Comment