Dare2Solve
This problem involves constructing a QuadTree from a given 2D binary grid. Each cell in the grid contains either a 0 or a 1. The QuadTree node is defined by the value it holds, whether it is a leaf node, and pointers to its four children (topLeft, topRight, bottomLeft, bottomRight). The objective is to recursively divide the grid into four equal parts until all parts contain the same value (either all 0s or all 1s) and construct the QuadTree accordingly.
The intuition behind constructing the QuadTree is to use a divide-and-conquer approach. We recursively split the grid into four sub-grids and check if all cells in a sub-grid have the same value. If they do, that part of the tree is a leaf node. If not, we further divide the sub-grid until we reach sub-grids with uniform values. This process ensures that the QuadTree accurately represents the grid with minimal nodes.
O(N^2 log N), where N is the dimension of the grid. The recursion involves splitting the grid log N times (depth of the QuadTree) and checking each cell in the grid at each level, leading to N^2 operations per level.
O(N^2), due to the space required for the recursion stack and the storage for the QuadTree nodes. The depth of the recursion stack can go up to log N, but in the worst case, every cell might need a node in the QuadTree.
class Solution {
public:
Node* recurse(vector<vector<int>>& grid, int si, int ei, int sj, int ej) {
int val = grid[si][sj];
Node* node = new Node();
node->val = val;
for (int i = si; i < ei; i++) {
for (int j = sj; j < ej; j++) {
if (grid[i][j] != val) {
node->isLeaf = false;
int midI = si + (ei - si) / 2;
int midJ = sj + (ej - sj) / 2;
node->topLeft = recurse(grid, si, midI, sj, midJ);
node->topRight = recurse(grid, si, midI, midJ, ej);
node->bottomLeft = recurse(grid, midI, ei, sj, midJ);
node->bottomRight = recurse(grid, midI, ei, midJ, ej);
return node;
}
}
}
node->isLeaf = true;
node->topLeft = nullptr;
node->topRight = nullptr;
node->bottomLeft = nullptr;
node->bottomRight = nullptr;
return node;
}
Node* construct(vector<vector<int>>& grid) {
return recurse(grid, 0, grid.size(), 0, grid[0].size());
}
};
class Solution:
def construct(self, grid: List[List[int]]) -> 'Node':
return self.recurse(grid, 0, len(grid), 0, len(grid[0]))
def recurse(self, grid: List[List[int]], si: int, ei: int, sj: int, ej: int) -> 'Node':
val = grid[si][sj]
node = Node(val == 1, True)
for i in range(si, ei):
for j in range(sj, ej):
if grid[i][j] != val:
node.isLeaf = False
midI = si + (ei - si) // 2
midJ = sj + (ej - sj) // 2
node.topLeft = self.recurse(grid, si, midI, sj, midJ)
node.topRight = self.recurse(grid, si, midI, midJ, ej)
node.bottomLeft = self.recurse(grid, midI, ei, sj, midJ)
node.bottomRight = self.recurse(grid, midI, ei, midJ, ej)
return node
node.isLeaf = True
node.topLeft = None
node.topRight = None
node.bottomLeft = None
node.bottomRight = None
return node
class Solution {
public Node construct(int[][] grid) {
return recurse(grid, 0, grid.length, 0, grid[0].length);
}
private Node recurse(int[][] grid, int si, int ei, int sj, int ej) {
int val = grid[si][sj];
Node node = new Node();
node.val = val == 1; // Convert int to boolean
for (int i = si; i < ei; i++) {
for (int j = sj; j < ej; j++) {
if (grid[i][j] != val) {
node.isLeaf = false;
int midI = si + (ei - si) / 2;
int midJ = sj + (ej - sj) / 2;
node.topLeft = recurse(grid, si, midI, sj, midJ);
node.topRight = recurse(grid, si, midI, midJ, ej);
node.bottomLeft = recurse(grid, midI, ei, sj, midJ);
node.bottomRight = recurse(grid, midI, ei, midJ, ej);
return node;
}
}
}
node.isLeaf = true;
node.topLeft = null;
node.topRight = null;
node.bottomLeft = null;
node.bottomRight = null;
return node;
}
}
let recurse = (grid, si, ei, sj, ej) => {
let val = grid[si][sj];
let node = new Node();
node.val = val;
for (let i = si; i < ei; i++) {
for (let j = sj; j < ej; j++) {
if (grid[i][j] !== val) {
node.isLeaf = false;
node.topLeft = recurse(grid, si, si + (ei - si) / 2, sj, sj + ((ej - sj) / 2));
node.topRight = recurse(grid, si, si + (ei - si) / 2, sj + (ej - sj) / 2, ej);
node.bottomLeft = recurse(grid, si + (ei - si) / 2, ei, sj, sj + (ej - sj) / 2);
node.bottomRight = recurse(grid, si + (ei - si) / 2, ei, sj + (ej - sj) / 2, ej);
return node;
}
}
}
node.isLeaf = true;
node.topLeft = null;
node.topRight = null;
node.bottomLeft = null;
node.bottomRight = null;
return node;
}
var construct = function (grid) {
let tree = recurse(grid, 0, grid.length, 0, grid.length);
return tree
};
``