Construct Quad Tree

This approach directly implements the recursive definition of the Quad Tree construction. A helper function is defined that takes the coordinates and size of the current sub-grid. This function first checks if all values in the sub-grid are the same. If they are, it creates a leaf node. If not, it creates an internal node, divides the grid into four equal quadrants, and makes a recursive call for each quadrant to build the sub-trees.

• Create a recursive helper function build(grid, row, col, size).
• In the helper function, check if the sub-grid from (row, col) of size x size is homogeneous.
• To check for homogeneity, iterate through all size * size cells and compare them to the first cell's value.
• If the sub-grid is homogeneous, create and return a leaf node with isLeaf=true and val set to the common value.
• If the sub-grid is not homogeneous, create an internal node with isLeaf=false.
• Recursively call build for the four quadrants:
  • topLeft = build(grid, row, col, size/2)
  • topRight = build(grid, row, col + size/2, size/2)
  • bottomLeft = build(grid, row + size/2, col, size/2)
  • bottomRight = build(grid, row + size/2, col + size/2, size/2)
• Assign the results to the children of the internal node and return it.
• The initial call is construct(grid) which calls build(grid, 0, 0, grid.length).

The core of this method is a recursive function, let's call it build(row, col, size). This function is responsible for constructing the Quad Tree for the size x size sub-grid starting at (row, col).

The process within build(row, col, size) is as follows:

1. Homogeneity Check: First, we determine if the sub-grid is homogeneous (contains all 0s or all 1s). We can do this by taking the value of the top-left cell, grid[row][col], and then iterating through all the cells in the size x size sub-grid. If we find any cell with a different value, the grid is not homogeneous.
2. Leaf Node Creation: If the check passes (the grid is homogeneous), we create a new Node. We set isLeaf to true, val to the common value (true for 1, false for 0), and all four children pointers to null. This node is then returned.
3. Internal Node Creation: If the check fails (the grid has mixed values), we create an internal node. We set isLeaf to false and val to an arbitrary value (e.g., true). Then, we divide the current size x size grid into four (size/2) x (size/2) sub-grids and make recursive calls to build for each of these four sub-grids, assigning the returned nodes to the topLeft, topRight, bottomLeft, and bottomRight children of the current internal node. This node is then returned.

The initial call to start the process would be build(0, 0, n), where n is the dimension of the input grid.

class Solution {
    public Node construct(int[][] grid) {
        return build(grid, 0, 0, grid.length);
    }

    private Node build(int[][] grid, int row, int col, int size) {
        // Check if the sub-grid is homogeneous
        boolean isHomogeneous = true;
        int firstVal = grid[row][col];
        for (int i = row; i < row + size; i++) {
            for (int j = col; j < col + size; j++) {
                if (grid[i][j] != firstVal) {
                    isHomogeneous = false;
                    break;
                }
            }
            if (!isHomogeneous) {
                break;
            }
        }

        if (isHomogeneous) {
            return new Node(firstVal == 1, true, null, null, null, null);
        } else {
            int newSize = size / 2;
            Node topLeft = build(grid, row, col, newSize);
            Node topRight = build(grid, row, col + newSize, newSize);
            Node bottomLeft = build(grid, row + newSize, col, newSize);
            Node bottomRight = build(grid, row + newSize, col + newSize, newSize);
            // The 'val' for an internal node can be arbitrary, e.g., true.
            return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
        }
    }
}