LeetCode 427: Construct Quad Tree Solution

Master LeetCode problem 427 (Construct Quad Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

427. Construct Quad Tree

Medium

Array Divide and Conquer Tree Matrix

Problem Explanation

Explanation

We can solve this problem recursively by checking if the current grid is a leaf node or not.
If the grid is a leaf node (only contains 0's or 1's), we create a leaf node with the value and set isLeaf to true.
If the grid is not a leaf node, we create a non-leaf node and divide the grid into four sub-grids.
Recursively construct Quad Trees for each sub-grid and assign them to the corresponding children of the current node.

Time Complexity

The time complexity of this approach is O(n^2) where n is the size of the grid.

Space Complexity

The space complexity is O(n^2) for the recursive stack.

Solution Code

class Solution {
    public Node construct(int[][] grid) {
        return constructHelper(grid, 0, 0, grid.length);
    }
    
    private Node constructHelper(int[][] grid, int row, int col, int size) {
        if (size <= 0) return null;
        
        boolean isLeaf = true;
        int val = grid[row][col];
        for (int i = row; i < row + size; i++) {
            for (int j = col; j < col + size; j++) {
                if (grid[i][j] != val) {
                    isLeaf = false;
                    break;
                }
            }
            if (!isLeaf) break;
        }
        
        if (isLeaf) {
            return new Node(val == 1, true, null, null, null, null);
        }
        
        int newSize = size / 2;
        Node topLeft = constructHelper(grid, row, col, newSize);
        Node topRight = constructHelper(grid, row, col + newSize, newSize);
        Node bottomLeft = constructHelper(grid, row + newSize, col, newSize);
        Node bottomRight = constructHelper(grid, row + newSize, col + newSize, newSize);
        
        return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 427 (Construct Quad Tree)?

This page provides optimized solutions for LeetCode problem 427 (Construct Quad Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 427 (Construct Quad Tree)?

The time complexity for LeetCode 427 (Construct Quad Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 427 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 427 in Java, C++, or Python.

Back to LeetCode Solutions