Sponsored
Sponsored
This approach involves recursively dividing the grid into four quadrants until each subdivision is either uniform (composed of the same elements) or a minimum size is reached. The base case of the recursion is when the grid section being considered is uniform, guiding us to create a leaf node. Otherwise, you recursively create non-leaf nodes and divide the grid further.
Time Complexity: O(n^2 * log(n)), where n is the length of the grid. Each division checks floor(n^2) cells for uniformity.
Space Complexity: O(log(n)), due to the recursion stack depth.
1class Node:
2 def __init__(self, val, isLeaf, topLeft=None, topRight=None, bottomLeft=None, bottomRight=None):
3 self.val = val
4 self.isLeaf = isLeaf
5 self.topLeft = topLeft
6 self.topRight = topRight
7 self.bottomLeft = bottomLeft
8 self.bottomRight = bottomRight
9
10def construct(grid):
11 def is_uniform(grid, x, y, size):
12 value = grid[x][y]
13 for i in range(x, x + size):
14 for j in range(y, y + size):
15 if grid[i][j] != value:
16 return False
17 return True
18
19 def construct_quad_tree(x, y, size):
20 if size == 1 or is_uniform(grid, x, y, size):
21 return Node(grid[x][y] == 1, True)
22 half = size // 2
23 topLeft = construct_quad_tree(x, y, half)
24 topRight = construct_quad_tree(x, y + half, half)
25 bottomLeft = construct_quad_tree(x + half, y, half)
26 bottomRight = construct_quad_tree(x + half, y + half, half)
27 return Node(True, False, topLeft, topRight, bottomLeft, bottomRight)
28
29 return construct_quad_tree(0, 0, len(grid))This solution defines a tree node class and a function to recursively construct the Quad-Tree. The function checks if a block in the grid is uniform and creates nodes accordingly, returning the root of the constructed tree.
This approach involves using a queue data structure for constructing the Quad-Tree iteratively. Initially, you enqueue the entire grid with its coordinates. By dequeuing elements and checking uniformity, you either create a leaf node or enqueue its four sub-regions for further processing.
Time Complexity: O(n^2), as each entry in the grid must be visited to verify uniformity.
Space Complexity: O(n^2) in the worst case, since there's a possibility of storing every grid block in separate nodes.
1#include <iostream>
2#include <queue>
3#include <vector>
4
5using namespace std;
class Node {
public:
bool val;
bool isLeaf;
Node* topLeft = nullptr;
Node* topRight = nullptr;
Node* bottomLeft = nullptr;
Node* bottomRight = nullptr;
Node(bool _val, bool _isLeaf) : val(_val), isLeaf(_isLeaf) {}
};
class Solution {
public:
Node* construct(vector<vector<int>>& grid) {
int n = grid.size();
return construct(0, 0, n, grid);
}
private:
Node* construct(int x, int y, int size, vector<vector<int>>& grid) {
if (size == 1) {
return new Node(grid[x][y] == 1, true);
}
int half = size / 2;
Node* topLeft = construct(x, y, half, grid);
Node* topRight = construct(x, y + half, half, grid);
Node* bottomLeft = construct(x + half, y, half, grid);
Node* bottomRight = construct(x + half, y + half, half, grid);
if (topLeft->isLeaf && topRight->isLeaf && bottomLeft->isLeaf && bottomRight->isLeaf &&
topLeft->val == topRight->val && topRight->val == bottomLeft->val && bottomLeft->val == bottomRight->val) {
return new Node(topLeft->val, true);
}
return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
}
};The C++ solution utilizes an iterative technique by gradually processing nodes via a queue. Each iteration checks for uniform grids, constructing either leaf or non-leaf nodes, and breaks down non-uniform areas for further examination.