# Untitled

unknown
java
20 days ago
2.4 kB
2
Indexable
Never
```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);
}
}```