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.
1function Node(val, isLeaf, topLeft, topRight,
This JavaScript solution mirrors the iterative approach by using ternary tree nodes. It handles grid divisions through iterative checks to determine if a section needs further breakdown, organizing components via nested loops.