• 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 27 class Solution { public: Node* construct(vector>& grid) { return helper(grid, 0, 0, grid.size()); } private: Node* helper(const vector>& 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>& grid, int i, int j, int w) { return all_of(begin(grid) + i, begin(grid) + i + w, [&](const vector& row) { return all_of(begin(row) + j, begin(row) + 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 25 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; } }