427. Construct Quad Tree

Description

This problem involves constructing a QuadTree from a given 2D binary grid. Each cell in the grid contains either a 0 or a 1. The QuadTree node is defined by the value it holds, whether it is a leaf node, and pointers to its four children (topLeft, topRight, bottomLeft, bottomRight). The objective is to recursively divide the grid into four equal parts until all parts contain the same value (either all 0s or all 1s) and construct the QuadTree accordingly.

Intuition

The intuition behind constructing the QuadTree is to use a divide-and-conquer approach. We recursively split the grid into four sub-grids and check if all cells in a sub-grid have the same value. If they do, that part of the tree is a leaf node. If not, we further divide the sub-grid until we reach sub-grids with uniform values. This process ensures that the QuadTree accurately represents the grid with minimal nodes.

Approach

1. Base Case: - If the grid is empty or all values in the current sub-grid are the same, create a leaf node with the corresponding value.
2. Recursive Case: - If the values in the current sub-grid are not the same, split the grid into four equal parts. - Recursively process each sub-grid to determine if it is a leaf or needs further splitting. - Create a non-leaf node and assign the four processed sub-grids as its children.
3. Implementation: - Start from the entire grid. - Use a helper function to recursively construct the QuadTree by checking each sub-grid's values. - Construct nodes accordingly, either as leaf nodes or internal nodes with children.

Complexity

Time Complexity:

O(N^2 log N), where N is the dimension of the grid. The recursion involves splitting the grid log N times (depth of the QuadTree) and checking each cell in the grid at each level, leading to N^2 operations per level.

Space Complexity:

O(N^2), due to the space required for the recursion stack and the storage for the QuadTree nodes. The depth of the recursion stack can go up to log N, but in the worst case, every cell might need a node in the QuadTree.

Code

C++

class Solution {
public:
    Node* recurse(vector>& grid, int si, int ei, int sj, int ej) {
        int val = grid[si][sj];
        Node* node = new Node();
        node->val = val;
        for (int i = si; i < ei; i++) {
            for (int j = sj; j < ej; j++) {
                if (grid[i][j] != val) {
                    node->isLeaf = false;
                    int midI = si + (ei - si) / 2;
                    int midJ = sj + (ej - sj) / 2;
                    node->topLeft = recurse(grid, si, midI, sj, midJ);
                    node->topRight = recurse(grid, si, midI, midJ, ej);
                    node->bottomLeft = recurse(grid, midI, ei, sj, midJ);
                    node->bottomRight = recurse(grid, midI, ei, midJ, ej);
                    return node;
                }
            }
        }
        node->isLeaf = true;
        node->topLeft = nullptr;
        node->topRight = nullptr;
        node->bottomLeft = nullptr;
        node->bottomRight = nullptr;
        return node;
    }

    Node* construct(vector>& grid) {
        return recurse(grid, 0, grid.size(), 0, grid[0].size());
    }
};

Python

class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        return self.recurse(grid, 0, len(grid), 0, len(grid[0]))
    
    def recurse(self, grid: List[List[int]], si: int, ei: int, sj: int, ej: int) -> 'Node':
        val = grid[si][sj]
        node = Node(val == 1, True)
        for i in range(si, ei):
            for j in range(sj, ej):
                if grid[i][j] != val:
                    node.isLeaf = False
                    midI = si + (ei - si) // 2
                    midJ = sj + (ej - sj) // 2
                    node.topLeft = self.recurse(grid, si, midI, sj, midJ)
                    node.topRight = self.recurse(grid, si, midI, midJ, ej)
                    node.bottomLeft = self.recurse(grid, midI, ei, sj, midJ)
                    node.bottomRight = self.recurse(grid, midI, ei, midJ, ej)
                    return node
        node.isLeaf = True
        node.topLeft = None
        node.topRight = None
        node.bottomLeft = None
        node.bottomRight = None
        return node

Java

class Solution {
    public Node construct(int[][] grid) {
        return recurse(grid, 0, grid.length, 0, grid[0].length);
    }
    
    private Node recurse(int[][] grid, int si, int ei, int sj, int ej) {
        int val = grid[si][sj];
        Node node = new Node();
        node.val = val == 1; // Convert int to boolean
        for (int i = si; i < ei; i++) {
            for (int j = sj; j < ej; j++) {
                if (grid[i][j] != val) {
                    node.isLeaf = false;
                    int midI = si + (ei - si) / 2;
                    int midJ = sj + (ej - sj) / 2;
                    node.topLeft = recurse(grid, si, midI, sj, midJ);
                    node.topRight = recurse(grid, si, midI, midJ, ej);
                    node.bottomLeft = recurse(grid, midI, ei, sj, midJ);
                    node.bottomRight = recurse(grid, midI, ei, midJ, ej);
                    return node;
                }
            }
        }
        node.isLeaf = true;
        node.topLeft = null;
        node.topRight = null;
        node.bottomLeft = null;
        node.bottomRight = null;
        return node;
    }
}

JavaScript

let recurse = (grid, si, ei, sj, ej) => {
    let val = grid[si][sj];
    let node = new Node();
    node.val = val;
    for (let i = si; i < ei; i++) {
        for (let j = sj; j < ej; j++) {
            if (grid[i][j] !== val) {
                node.isLeaf = false;
                node.topLeft = recurse(grid, si, si + (ei - si) / 2, sj, sj + ((ej - sj) / 2));
                node.topRight = recurse(grid, si, si + (ei - si) / 2, sj + (ej - sj) / 2, ej);
                node.bottomLeft = recurse(grid, si + (ei - si) / 2, ei, sj, sj + (ej - sj) / 2);
                node.bottomRight = recurse(grid, si + (ei - si) / 2, ei, sj + (ej - sj) / 2, ej);
                return node;
            }
        }
    }
    node.isLeaf = true;
    node.topLeft = null;
    node.topRight = null;
    node.bottomLeft = null;
    node.bottomRight = null;
    return node;
}

var construct = function (grid) {
    let tree = recurse(grid, 0, grid.length, 0, grid.length);
    return tree
};
``