LeetCodee

427. Construct Quad Tree

Jump to Solution: Python Java C++ JavaScript C#

Problem Description

Given a n * n matrix grid of 0's and 1's, construct a quad-tree representation of the grid.

Each node of the quad-tree has the following properties:

val: True if the node represents a grid of 1's or False if the node represents a grid of 0's.
isLeaf: True if the node is a leaf node on the tree or False if the node has four children.
topLeft, topRight, bottomLeft, bottomRight: The four children nodes of the node.

Example 1:

Input: grid = [[0,1],[1,0]]
Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Explanation: The explanation of this example is shown below:
Notice that 0 represents False and 1 represents True in the quad-tree representation.

Example 2:

Input: grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
Output: [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]

Constraints:

n == grid.length == grid[i].length
n == 2ⁿ where 0 <= x <= 6

Solution

Python Solution

class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        def isLeaf(x: int, y: int, n: int) -> bool:
            # Check if all values in this quadrant are the same
            val = grid[x][y]
            for i in range(x, x + n):
                for j in range(y, y + n):
                    if grid[i][j] != val:
                        return False
            return True
        
        def helper(x: int, y: int, n: int) -> 'Node':
            # If this is a leaf node, return it
            if isLeaf(x, y, n):
                return Node(grid[x][y] == 1, True)
            
            # Otherwise, split into four quadrants
            n = n // 2
            topLeft = helper(x, y, n)
            topRight = helper(x, y + n, n)
            bottomLeft = helper(x + n, y, n)
            bottomRight = helper(x + n, y + n, n)
            
            return Node(True, False, topLeft, topRight, bottomLeft, bottomRight)
        
        n = len(grid)
        return helper(0, 0, n)

Time Complexity: O(n²)

Where n is the length of the grid. We need to check each cell at least once.

Space Complexity: O(log n)

For the recursion stack depth.

Java Solution

class Solution {
    private int[][] grid;
    
    public Node construct(int[][] grid) {
        this.grid = grid;
        return helper(0, 0, grid.length);
    }
    
    private boolean isLeaf(int x, int y, int n) {
        // Check if all values in this quadrant are the same
        int val = grid[x][y];
        for (int i = x; i < x + n; i++) {
            for (int j = y; j < y + n; j++) {
                if (grid[i][j] != val) {
                    return false;
                }
            }
        }
        return true;
    }
    
    private Node helper(int x, int y, int n) {
        // If this is a leaf node, return it
        if (isLeaf(x, y, n)) {
            return new Node(grid[x][y] == 1, true);
        }
        
        // Otherwise, split into four quadrants
        n = n / 2;
        Node topLeft = helper(x, y, n);
        Node topRight = helper(x, y + n, n);
        Node bottomLeft = helper(x + n, y, n);
        Node bottomRight = helper(x + n, y + n, n);
        
        return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
    }
}

Time Complexity: O(n²)

Where n is the length of the grid. We need to check each cell at least once.

Space Complexity: O(log n)

For the recursion stack depth.

C++ Solution

class Solution {
private:
    vector> grid;
    
    bool isLeaf(int x, int y, int n) {
        // Check if all values in this quadrant are the same
        int val = grid[x][y];
        for (int i = x; i < x + n; i++) {
            for (int j = y; j < y + n; j++) {
                if (grid[i][j] != val) {
                    return false;
                }
            }
        }
        return true;
    }
    
    Node* helper(int x, int y, int n) {
        // If this is a leaf node, return it
        if (isLeaf(x, y, n)) {
            return new Node(grid[x][y], true);
        }
        
        // Otherwise, split into four quadrants
        n = n / 2;
        Node* topLeft = helper(x, y, n);
        Node* topRight = helper(x, y + n, n);
        Node* bottomLeft = helper(x + n, y, n);
        Node* bottomRight = helper(x + n, y + n, n);
        
        return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
    }
    
public:
    Node* construct(vector>& grid) {
        this.grid = grid;
        return helper(0, 0, grid.size());
    }
};

Time Complexity: O(n²)

Where n is the length of the grid. We need to check each cell at least once.

Space Complexity: O(log n)

For the recursion stack depth.

JavaScript Solution

/**
 * @param {number[][]} grid
 * @return {Node}
 */
var construct = function(grid) {
    function isLeaf(x, y, n) {
        // Check if all values in this quadrant are the same
        const val = grid[x][y];
        for (let i = x; i < x + n; i++) {
            for (let j = y; j < y + n; j++) {
                if (grid[i][j] !== val) {
                    return false;
                }
            }
        }
        return true;
    }
    
    function helper(x, y, n) {
        // If this is a leaf node, return it
        if (isLeaf(x, y, n)) {
            return new Node(grid[x][y] === 1, true);
        }
        
        // Otherwise, split into four quadrants
        n = n / 2;
        const topLeft = helper(x, y, n);
        const topRight = helper(x, y + n, n);
        const bottomLeft = helper(x + n, y, n);
        const bottomRight = helper(x + n, y + n, n);
        
        return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
    }
    
    return helper(0, 0, grid.length);
};

Time Complexity: O(n²)

Where n is the length of the grid. We need to check each cell at least once.

Space Complexity: O(log n)

For the recursion stack depth.

C# Solution

public class Solution {
    private int[][] grid;
    
    public Node Construct(int[][] grid) {
        this.grid = grid;
        return Helper(0, 0, grid.Length);
    }
    
    private bool IsLeaf(int x, int y, int n) {
        // Check if all values in this quadrant are the same
        int val = grid[x][y];
        for (int i = x; i < x + n; i++) {
            for (int j = y; j < y + n; j++) {
                if (grid[i][j] != val) {
                    return false;
                }
            }
        }
        return true;
    }
    
    private Node Helper(int x, int y, int n) {
        // If this is a leaf node, return it
        if (IsLeaf(x, y, n)) {
            return new Node(grid[x][y] == 1, true);
        }
        
        // Otherwise, split into four quadrants
        n = n / 2;
        Node topLeft = Helper(x, y, n);
        Node topRight = Helper(x, y + n, n);
        Node bottomLeft = Helper(x + n, y, n);
        Node bottomRight = Helper(x + n, y + n, n);
        
        return new Node(true, false, topLeft, topRight, bottomLeft, bottomRight);
    }
}

Time Complexity: O(n²)

Where n is the length of the grid. We need to check each cell at least once.

Space Complexity: O(log n)

For the recursion stack depth.

Approach Explanation

The solution uses a recursive divide-and-conquer approach:

Key Insights:
- Recursive division
- Quadrant checking
- Leaf detection
- Tree construction
Algorithm Steps:
- Check leaf status
- Divide grid
- Recursive construction
- Node linking

Implementation Details:

Grid traversal
Value checking
Node creation
Recursion handling

Optimization Insights:

Early termination
Space efficiency
Quadrant division
Memory reuse

Edge Cases:

Single cell
All same values
Mixed values
Large grids