Solution For Construct Quad Tree
Construct Quad Tree is a problem on LeetCode that requires you to efficiently create a Quad Tree, a tree data structure that is used to represent an image, grid or any two-dimensional data. In this data structure, each node has four children, which are either null or represent a quarter of the parent cell. The problem description is as follows:
Given a n * n matrix grid of 0’s and 1’s, create a quad tree that represents its black and white pixels.
Return the root of the quad tree.
Note that you cannot use the trivial solution of creating a Quad Tree node for each pixel, as the input size can be as large as 10^9.
To efficiently solve this problem, we need to use a divide-and-conquer approach. The idea is to recursively divide the matrix into four quadrants, create a Quad Tree node for each quadrant, and assign it to the parent node.
To implement this solution, we need to define a Quad Tree class that has the following properties:
- Value: 0 or 1, depending on the quadrant being represented.
- Children: A list of four Quad Tree nodes that represent the four quadrants of the parent node.
We can use the following algorithm to create the Quad Tree:
Check if all the pixels in the matrix have the same value. If yes, create a Quad Tree node with the same value and return it.
If not, divide the matrix into four quadrants (top-left, top-right, bottom-left, and bottom-right).
Recursively create Quad Tree nodes for each quadrant using steps #1 to #3.
Create a Quad Tree node for the parent node and assign its children to the Quad Tree nodes created in step #3.
Return the root of the Quad Tree.
Here’s the Python code that implements the above algorithm:
“`
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: List[List[int]]) -> ‘Node’:
n = len(grid)
if n == 0:
return None
if n == 1:
return Node(grid[0][0], True, None, None, None, None)
if all(grid[i][j] == grid[0][0] for i in range(n) for j in range(n)):
return Node(grid[0][0], True, None, None, None, None)
m = n // 2
topLeft = self.construct([row[:m] for row in grid[:m]])
topRight = self.construct([row[m:] for row in grid[:m]])
bottomLeft = self.construct([row[:m] for row in grid[m:]])
bottomRight = self.construct([row[m:] for row in grid[m:]])
return Node(‘*’,
False,
topLeft,
topRight,
bottomLeft,
bottomRight)
“`
The code first checks if the matrix has only one pixel or if all pixels have the same value. If yes, it creates a Quad Tree node with the same value and returns it.
Otherwise, the code recursively divides the matrix into four quadrants and creates Quad Tree nodes for each quadrant using the same algorithm, and then assigns them to the parent node. The parent node is then returned.
This algorithm has a time complexity of O(n^2 log n), as we need to recursively divide the matrix into four quadrants until we reach a 1×1 grid. However, we only process each pixel once, so the algorithm has a space complexity of O(n^2).
Step by Step Implementation For Construct Quad Tree
/*
// 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,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(int[][] g) {
return build(g, 0, 0, g.length);
}
private Node build(int[][] g, int x, int y, int len) {
if (len == 1) {
return new Node(g[x][y] != 0, true, null, null, null, null);
}
int half = len / 2;
Node topLeft = build(g, x, y, half);
Node topRight = build(g, x, y + half, half);
Node bottomLeft = build(g, x + half, y, half);
Node bottomRight = build(g, x + half, y + half, half);
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, null, null, null, null);
}
return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
}
}# 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):
"""
:type grid: List[List[int]]
:rtype: Node
"""
# Your code here
# Base case - when we reach a 1x1 grid
if len(grid) == 1:
# If the single element in the grid is a 0, then this node is a leaf node with val = 0
if grid[0][0] == 0:
return Node(val = 0, isLeaf = True, topLeft = None, topRight = None, bottomLeft = None, bottomRight = None)
# If the single element in the grid is a 1, then this node is a leaf node with val = 1
else:
return Node(val = 1, isLeaf = True, topLeft = None, topRight = None, bottomLeft = None, bottomRight = None)
# Recursive case - when we have a grid of size > 1
else:
# Find the midpoints of the grid
mid_row = len(grid) // 2
mid_col = len(grid[0]) // 2
# Split the grid into 4 quadrants
# Top left quadrant
top_left = []
for i in range(mid_row):
top_left.append(grid[i][:mid_col])
# Top right quadrant
top_right = []
for i in range(mid_row):
top_right.append(grid[i][mid_col:])
# Bottom left quadrant
bottom_left = []
for i in range(mid_row, len(grid)):
bottom_left.append(grid[i][:mid_col])
# Bottom right quadrant
bottom_right = []
for i in range(mid_row, len(grid)):
bottom_right.append(grid[i][mid_col:])
# Construct the node
# If all quadrants are leaf nodes with the same value, then this node is a leaf node with that value
# Otherwise, this node is an internal node with the 4 quadrants as its children
if self.is_leaf(top_left) and self.is_leaf(top_right) and self.is_leaf(bottom_left) and self.is_leaf(bottom_right):
if top_left[0][0] == 1:
return Node(val = 1, isLeaf = True, topLeft = None, topRight = None, bottomLeft = None, bottomRight = None)
else:
return Node(val = 0, isLeaf = True, topLeft = None, topRight = None, bottomLeft = None, bottomRight = None)
else:
return Node(val = None, isLeaf = False, topLeft = self.construct(top_left), topRight = self.construct(top_right), bottomLeft = self.construct(bottom_left), bottomRight = self.construct(bottom_right))
# Helper function to check if a grid is a leaf node
def is_leaf(self, grid):
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] != grid[0][0]:
return False
return True// Definition for a QuadTree node.
function Node(val,isLeaf,topLeft,topRight,bottomLeft,bottomRight) {
this.val = val;
this.isLeaf = isLeaf;
this.topLeft = topLeft;
this.topRight = topRight;
this.bottomLeft = bottomLeft;
this.bottomRight = bottomRight;
};
/**
* @param {number[][]} grid
* @return {Node}
*/
var construct = function(grid) {
// if the grid is empty, return null
if (grid.length === 0) return null;
// if the grid has only one element, return a leaf node
if (grid.length === 1) {
let val = grid[0][0];
let isLeaf = true;
let topLeft = null;
let topRight = null;
let bottomLeft = null;
let bottomRight = null;
return new Node(val, isLeaf, topLeft, topRight, bottomLeft, bottomRight);
}
// otherwise, split the grid into four subgrids
let topLeftGrid = [];
let topRightGrid = [];
let bottomLeftGrid = [];
let bottomRightGrid = [];
// populate the subgrids
for (let i = 0; i < grid.length / 2; i++) {
topLeftGrid.push([]);
topRightGrid.push([]);
bottomLeftGrid.push([]);
bottomRightGrid.push([]);
for (let j = 0; j < grid.length / 2; j++) {
topLeftGrid[i].push(grid[i][j]);
}
for (let j = grid.length / 2; j < grid.length; j++) {
topRightGrid[i].push(grid[i][j]);
}
for (let j = 0; j < grid.length / 2; j++) {
bottomLeftGrid[i].push(grid[i + grid.length / 2][j]);
}
for (let j = grid.length / 2; j < grid.length; j++) {
bottomRightGrid[i].push(grid[i + grid.length / 2][j]);
}
}
// recursively build the quad tree for each subgrid
let topLeft = construct(topLeftGrid);
let topRight = construct(topRightGrid);
let bottomLeft = construct(bottomLeftGrid);
let bottomRight = construct(bottomRightGrid);
// if all four subgrids have the same value, then this node is a leaf node
if (topLeft.val === topRight.val && topRight.val === bottomLeft.val && bottomLeft.val === bottomRight.val) {
let val = topLeft.val;
let isLeaf = true;
return new Node(val, isLeaf, topLeft, topRight, bottomLeft, bottomRight);
}
// otherwise, this node is not a leaf node
let val = null;
let isLeaf = false;
return new Node(val, isLeaf, topLeft, topRight, bottomLeft, bottomRight);
};We can solve this problem by using a quadtree data structure. A quadtree is a tree data structure in which each node has four children. The quadtree can be used to represent a two-dimensional space. In this leetcode problem, we are given a 2D array of 0s and 1s. We can use a quadtree to represent this 2D array. The root of the quadtree will represent the entire 2D array. The four children of the root will represent the four quadrants of the 2D array. If a quadrant contains only 0s, then we can represent it as a leaf node. Otherwise, we will need to further subdivide that quadrant into four smaller quadrants. We can continue this process until all quadrants only contain 0s or 1s.
Here is some pseudocode for this algorithm:
QuadtreeNode* constructQuadtree(int[][] grid) {
if (grid is empty) {
return null;
}
// create root node
QuadtreeNode* root = new QuadtreeNode();
// recursively construct the quadtree
root->construct(grid, 0, 0, grid.length, grid[0].length);
return root;
}
QuadtreeNode::construct(int[][] grid, int x, int y, int width, int height) {
// base case: quadrant contains only 0s or 1s
if (quadrantContainsOnly0sOr1s(grid, x, y, width, height)) {
this->val = quadrantContainsOnly0s(grid, x, y, width, height) ? 0 : 1;
return;
}
// otherwise, subdivide quadrant into four smaller quadrants
this->val = 1;
this->topLeft = new QuadtreeNode();
this->topRight = new QuadtreeNode();
this->bottomLeft = new QuadtreeNode();
this->bottomRight = new QuadtreeNode();
int newWidth = width / 2;
int newHeight = height / 2;
this->topLeft->construct(grid, x, y, newWidth, newHeight);
this->topRight->construct(grid, x + newWidth, y, newWidth, newHeight);
this->bottomLeft->construct(grid, x, y + newHeight, newWidth, newHeight);
this->bottomRight->construct(grid, x + newWidth, y + newHeight, newWidth, newHeight);
}
bool quadrantContainsOnly0sOr1s(int[][] grid, int x, int y, int width, int height) {
for (int i = x; i < x + width; i++) {
for (int j = y; j < y + height; j++) {
if (grid[i][j] != 0 && grid[i][j] != 1) {
return false;
}
}
}
return true;
}
bool quadrantContainsOnly0s(int[][] grid, int x, int y, int width, int height) {
for (int i = x; i < x + width; i++) {
for (int j = y; j < y + height; j++) {
if (grid[i][j] != 0) {
return false;
}
}
}
return true;
}We can use a QuadTree data structure to solve this problem. A QuadTree is a tree data structure in which each node has up to four children. In this problem, each node represents a square area of the grid. The root node represents the entire grid. If all the squares in a node's area are the same color, then that node is a leaf node and has no children. Otherwise, the node is a non-leaf node and has four children, each representing a quarter of the node's area. We can use a recursive algorithm to construct the QuadTree. We start by creating the root node. Then, we recursively call the algorithm on each of the four quadrants of the root node's area. If all the squares in a quadrant are the same color, then we create a leaf node for that quadrant. Otherwise, we create a non-leaf node and recursively call the algorithm on each of the quadrant's four quadrants. Here is the pseudocode for the algorithm: function constructQuadTree(grid, x, y, width, height): // Create the root node. node = new QuadTreeNode(x, y, width, height) // Recursively construct the QuadTree. for each quadrant in node.quadrants: if all squares in quadrant are the same color: // Create a leaf node for the quadrant. node.addChild(new QuadTreeNode(quadrant.x, quadrant.y, quadrant.width, quadrant.height)) else: // Create a non-leaf node for the quadrant. node.addChild(constructQuadTree(grid, quadrant.x, quadrant.y, quadrant.width, quadrant.height)) return node