"""
# Definition for a QuadTree node.
class Node:
def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
self.val = val
self.isLeaf = isLeaf
self.topLeft = topLeft
self.topRight = topRight
self.bottomLeft = bottomLeft
self.bottomRight = bottomRight
"""
class Solution:
def construct(self, grid):
def isUniform(x0, y0, length):
val = grid[x0][y0]
for i in range(x0, x0 + length):
for j in range(y0, y0 + length):
if grid[i][j] != val:
return False
return True
def build(x0, y0, length):
if isUniform(x0, y0, length):
return Node(grid[x0][y0] == 1, True, None, None, None, None)
half = length // 2
return Node(
True, False,
build(x0, y0, half),
build(x0, y0 + half, half),
build(x0 + half, y0, half),
build(x0 + half, y0 + half, half)
)
n = len(grid)
return build(0, 0, n)
/*
class Node {
public:
bool val;
bool isLeaf;
Node* topLeft;
Node* topRight;
Node* bottomLeft;
Node* bottomRight;
Node() : val(false), isLeaf(false), topLeft(NULL), topRight(NULL), bottomLeft(NULL), bottomRight(NULL) {}
Node(bool _val, bool _isLeaf) : val(_val), isLeaf(_isLeaf), topLeft(NULL), topRight(NULL), bottomLeft(NULL), bottomRight(NULL) {}
Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight)
: val(_val), isLeaf(_isLeaf), topLeft(_topLeft), topRight(_topRight), bottomLeft(_bottomLeft), bottomRight(_bottomRight) {}
};
*/
class Solution {
public:
Node* construct(vector>& grid) {
return build(grid, 0, 0, grid.size());
}
bool isUniform(vector>& grid, int x, int y, int length) {
int val = grid[x][y];
for (int i = x; i < x + length; ++i) {
for (int j = y; j < y + length; ++j) {
if (grid[i][j] != val) return false;
}
}
return true;
}
Node* build(vector>& grid, int x, int y, int length) {
if (isUniform(grid, x, y, length)) {
return new Node(grid[x][y] == 1, true);
}
int half = length / 2;
return new Node(
true, false,
build(grid, x, y, half),
build(grid, x, y + half, half),
build(grid, x + half, y, half),
build(grid, x + half, y + half, half)
);
}
};
/*
// 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() {}
public Node(boolean val, boolean isLeaf) {
this.val = val;
this.isLeaf = isLeaf;
}
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 Node construct(int[][] grid) {
return build(grid, 0, 0, grid.length);
}
private boolean isUniform(int[][] grid, int x, int y, int length) {
int val = grid[x][y];
for (int i = x; i < x + length; i++) {
for (int j = y; j < y + length; j++) {
if (grid[i][j] != val) return false;
}
}
return true;
}
private Node build(int[][] grid, int x, int y, int length) {
if (isUniform(grid, x, y, length)) {
return new Node(grid[x][y] == 1, true);
}
int half = length / 2;
return new Node(
true, false,
build(grid, x, y, half),
build(grid, x, y + half, half),
build(grid, x + half, y, half),
build(grid, x + half, y + half, half)
);
}
}
/*
class Node {
constructor(val, isLeaf, topLeft, topRight, bottomLeft, bottomRight) {
this.val = val;
this.isLeaf = isLeaf;
this.topLeft = topLeft;
this.topRight = topRight;
this.bottomLeft = bottomLeft;
this.bottomRight = bottomRight;
}
}
*/
var construct = function(grid) {
function isUniform(x, y, length) {
let val = grid[x][y];
for (let i = x; i < x + length; ++i) {
for (let j = y; j < y + length; ++j) {
if (grid[i][j] !== val) return false;
}
}
return true;
}
function build(x, y, length) {
if (isUniform(x, y, length)) {
return new Node(grid[x][y] === 1, true, null, null, null, null);
}
let half = length / 2;
return new Node(
true, false,
build(x, y, half),
build(x, y + half, half),
build(x + half, y, half),
build(x + half, y + half, half)
);
}
let n = grid.length;
return build(0, 0, n);
};
Given a n x n binary matrix grid (where each value is 0 or 1), construct a quad tree representation of this grid.
Each node in the quad tree represents a square region of the grid:
0 or all 1), the node is a leaf node with isLeaf = true and val set to the region's value.n == grid.length == grid[i].lengthn is a power of 2 (e.g. 1, 2, 4, 8, ...)grid[i][j] is 0 or 1
The problem asks us to recursively divide a binary matrix into quadrants until each region is uniform (all 0s or all 1s), and to represent this as a tree.
At first glance, a brute-force approach would be to check every possible sub-square, but that's not practical.
Instead, we can think recursively: for any square, if all its values are the same, it's a leaf. Otherwise, we split it into four smaller squares and repeat the process for each.
This is similar to how image compression or spatial indexing works, where we want to minimize the number of nodes by merging uniform regions. The key is to check for uniformity efficiently, and only split when necessary.
The solution uses a recursive divide-and-conquer strategy:
isLeaf = true and set val to the region's value.
isLeaf = false, and the four children are the results of the recursive calls.
Let's consider the following 2x2 grid:
[[1, 1],
[1, 0]]
Step 1: Check the whole grid (0,0)-(1,1). Not uniform (bottom-right is 0, rest are 1).
Step 2: Divide into four 1x1 quadrants:
Brute-force Approach:
If we naively checked all possible sub-squares, the time complexity would be exponential due to overlapping subproblems.
Optimized Recursive Approach:
For an n x n grid, at each recursion, we check O(n^2) cells for uniformity. The number of nodes in the quad tree is at most O(n^2) (since each cell could be its own leaf in the worst case).
O(n^2 log n) in the worst case (each level checks all cells in its region, and there are log n levels). In practice, it's closer to O(n^2) if many regions are uniform.O(n^2) for the quad tree nodes (worst case: every cell is a leaf).The quad tree construction problem uses a classic divide-and-conquer approach. By recursively splitting the grid and only creating new nodes when regions are not uniform, we efficiently represent the matrix in a compressed tree structure. The key insight is to check for uniformity at each step, allowing us to merge regions and minimize the number of nodes. This approach is both elegant and efficient, leveraging recursion to mirror the spatial structure of the grid.