Construct Quad Tree - Leetcode Solution

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:

1. 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.

2. If not, divide the matrix into four quadrants (top-left, top-right, bottom-left, and bottom-right).

3. Recursively create Quad Tree nodes for each quadrant using steps #1 to #3.

4. Create a Quad Tree node for the parent node and assign its children to the Quad Tree nodes created in step #3.

5. 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 1x1 grid. However, we only process each pixel once, so the algorithm has a space complexity of O(n^2).

1