Construct quad tree

Array Divide and Conquer Tree Matrix

78.1% acceptance

Jan 13, 2026

1746

1959

Given a n * n matrix grid of 0's and 1's only. We want to represent grid with a Quad-Tree. Return the root of the Quad-Tree representing grid.

Solution

C++

Time O(n)

Space O(1)

LeetCode

solution.cpp

class Solution {
  Node* build(vector<vector<int>>& grid, int r, int c, int n) {
    bool allSame = true;
    int val = grid[r][c];
    for (int i = r; i < r + n && allSame; i++)
      for (int j = c; j < c + n && allSame; j++)
        if (grid[i][j] != val) allSame = false;
    if (allSame) return new Node(val == 1, true);
    int half = n / 2;
    return new Node(true, false,
      build(grid, r, c, half),
      build(grid, r, c + half, half),
      build(grid, r + half, c, half),
      build(grid, r + half, c + half, half));
  }
public:
  Node* construct(vector<vector<int>>& grid) {
    return build(grid, 0, 0, grid.size());
  }
};