leetcode

0 class Solution {

1 public:

2 Node *construct(vector<vector<int>> &grid, int rowStart, int rowEnd, int colStart, int colEnd) {

3 if (rowStart > rowEnd || colStart > colEnd) return nullptr;

4

5 bool isLeaf = true;

6 int val = grid[rowStart][colStart];

7 for (int i = rowStart; i <= rowEnd; i++) {

8 for (int j = colStart; j <= colEnd; j++) {

9 if (grid[i][j] != val) {

10 isLeaf = false;

11 break;

12 }

13 }

14 if (!isLeaf) break;

15 }

16

17 if (isLeaf) return new Node(val, true);

18

19 int rowMid = (rowStart + rowEnd) / 2;

20 int colMid = (colStart + colEnd) / 2;

21 Node *topLeft = construct(grid, rowStart, rowMid, colStart, colMid);

22 Node *topRight = construct(grid, rowStart, rowMid, colMid + 1, colEnd);

23 Node *bottomLeft = construct(grid, rowMid + 1, rowEnd, colStart, colMid);

24 Node *bottomRight = construct(grid, rowMid + 1, rowEnd, colMid + 1, colEnd);

25 return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);

26 }

27 Node *construct(vector<vector<int>> &grid) {

28 int n = grid.size();

29 return construct(grid, 0, n - 1, 0, n - 1);

30 }

31 };