Skip to content

427. Construct Quad Tree 👎

  • Time: $O(n^2 \log_4 n)$
  • Space: $O(\log_4 n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  Node* construct(vector<vector<int>>& grid) {
    return helper(grid, 0, 0, grid.size());
  }

 private:
  Node* helper(const vector<vector<int>>& grid, int i, int j, int w) {
    if (allSame(grid, i, j, w))
      return new Node(grid[i][j] == 1, /*isLeaft=*/true);
    const int half = w / 2;
    return new Node(/*val=*/true, /*isLeaf=*/false,
                    /*topLeft=*/helper(grid, i, j, half),
                    /*topRight=*/helper(grid, i, j + half, half),
                    /*bottomLeft=*/helper(grid, i + half, j, half),
                    /*bottomRight=*/helper(grid, i + half, j + half, half));
  }

  bool allSame(const vector<vector<int>>& grid, int i, int j, int w) {
    return all_of(grid.begin() + i, grid.begin() + i + w,
                  [&](const vector<int>& row) {
      return all_of(row.begin() + j, row.begin() + j + w,
                    [&](int num) { return num == grid[i][j]; });
    });
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public Node construct(int[][] grid) {
    return helper(grid, 0, 0, grid.length);
  }

  private Node helper(int[][] grid, int i, int j, int w) {
    if (allSame(grid, i, j, w))
      return new Node(grid[i][j] == 1, /*isLeaf=*/true);
    final int half = w / 2;
    return new Node(/*val=*/true, /*isLeaf=*/false,
                    /*topLeft=*/helper(grid, i, j, half),
                    /*topRight=*/helper(grid, i, j + half, half),
                    /*bottomLeft=*/helper(grid, i + half, j, half),
                    /*bottomRight=*/helper(grid, i + half, j + half, half));
  }

  private boolean allSame(int[][] grid, int i, int j, int w) {
    for (int x = i; x < i + w; ++x)
      for (int y = j; y < j + w; ++y)
        if (grid[x][y] != grid[i][j])
          return false;
    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def construct(self, grid: list[list[int]]) -> 'Node':
    return self._helper(grid, 0, 0, len(grid))

  def _helper(self, grid: list[list[int]], i: int, j: int, w: int) -> 'Node':
    if self._allSame(grid, i, j, w):
      return Node(grid[i][j] == 1, True)
    half = w // 2
    return Node(True, False,
                self._helper(grid, i, j, half),
                self._helper(grid, i, j + half, half),
                self._helper(grid, i + half, j, half),
                self._helper(grid, i + half, j + half, half))

  def _allSame(self, grid: list[list[int]], i: int, j: int, w: int) -> bool:
    return all(grid[x][y] == grid[i][j]
               for x in range(i, i + w)
               for y in range(j, j + w))