Construct Quad Tree LeetCode solution in C++

1
class Solution {
2
 public:
3
  bool areValuesSame(vector<vector<int>> &grid, int rowStart, int rowEnd, int colStart,
4
                     int colEnd) {
5
    int val = grid[rowStart][colStart];
6
    for (int i = rowStart; i <= rowEnd; i++) {
7
      for (int j = colStart; j <= colEnd; j++) {
8
        if (grid[i][j] != val) return false;
9
      }
10
    }
11
    return true;
12
  }
13

14
  Node *helper(vector<vector<int>> &grid, int rowStart, int rowEnd, int colStart, int colEnd) {
15
    // New Node with isLeaf set to true by default
16
    Node *newNode = new Node(grid[rowStart][colStart], true);
17

18
    // Base Case if either the grid has only one cell or all the cell values are
19
    // same
20
    if ((rowStart == rowEnd && colStart == colEnd) ||
21
        areValuesSame(grid, rowStart, rowEnd, colStart, colEnd)) {
22
      return newNode;
23
    }
24

25
    // Set isLeaf to false as base case failed
26
    newNode->isLeaf = false;
27

28
    /* Consider variables rowMid and colMid to set the middle index between
29
    start and end of rows and columns of current grid portion*/
30
    int rowMid = rowStart + (rowEnd - rowStart) / 2;
31
    int colMid = colStart + (colEnd - colStart) / 2;
32

33
    // Recursively finding children of current node (newNode)
34
    newNode->topLeft = helper(grid, rowStart, rowMid, colStart, colMid);
35
    newNode->topRight = helper(grid, rowStart, rowMid, colMid + 1, colEnd);
36
    newNode->bottomLeft = helper(grid, rowMid + 1, rowEnd, colStart, colMid);
37
    newNode->bottomRight = helper(grid, rowMid + 1, rowEnd, colMid + 1, colEnd);
38

39
    return newNode;
40
  }
41

42
  Node *construct(vector<vector<int>> &grid) {
43
    int n = grid.size();
44
    return helper(grid, 0, n - 1, 0, n - 1);
45
  }
46
};