Untitled

unknown
java
20 days ago
3.1 kB
5
Indexable
Never
```/*
// 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);

}
}```