LeetCode Solutions
427. Construct Quad Tree
Time: $O(n^2 \log_4 n)$ Space: $O(\log_4 n)$
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], true);
Node* node = new Node(true, false);
node->topLeft = helper(grid, i, j, w / 2);
node->topRight = helper(grid, i, j + w / 2, w / 2);
node->bottomLeft = helper(grid, i + w / 2, j, w / 2);
node->bottomRight = helper(grid, i + w / 2, j + w / 2, w / 2);
return node;
}
bool allSame(const vector<vector<int>>& grid, int i, int j, int w) {
return all_of(begin(grid) + i, begin(grid) + i + w,
[&](const vector<int>& row) {
return all_of(begin(row) + j, begin(row) + j + w,
[&](int num) { return num == grid[i][j]; });
});
}
};
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 ? true : false, true);
Node node = new Node(true, false);
node.topLeft = helper(grid, i, j, w / 2);
node.topRight = helper(grid, i, j + w / 2, w / 2);
node.bottomLeft = helper(grid, i + w / 2, j, w / 2);
node.bottomRight = helper(grid, i + w / 2, j + w / 2, w / 2);
return node;
}
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;
}
}