题意：给你一个NN（N 为2的指数倍数）的矩形方阵，用一种叫做Quad Tree的数型结构表示。
解题思路：一个递归算法。
注意事项：在递归返回的时候，返回值需要用new Node（参，参，参，参，参，参）模型，因为使用new关键字开辟内存的时候，函数返回后内存不会被收走；如果使用普通的声明Node（，，，，，*）模式，该内存为临时内存，当函数返回的时候会将内存抹掉，出现内存访问错误。
/*
// Definition for a QuadTree node.
class Node {
public:
bool val;
bool isLeaf;
Node* topLeft;
Node* topRight;
Node* bottomLeft;
Node* bottomRight;
Node() {}
Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
val = _val;
isLeaf = _isLeaf;
topLeft = _topLeft;
topRight = _topRight;
bottomLeft = _bottomLeft;
bottomRight = _bottomRight;
}
};
*/
class Solution {
public:
Node* construct(vector<vector<int>>& grid) {
int sizeNum = grid.size();
return getQuad(grid, 0, 0, sizeNum, sizeNum);
}
Node* getQuad(vector<vector<int>>& grid, int startRow, int startCol, int endRow, int endCol){
bool flg = grid[startRow][startCol];
int sizeNum = (endRow - startRow) / 2;
int midRow = startRow + sizeNum;
int midCol = startCol + sizeNum;
for(int i = startRow; i < endRow; i++){
for(int j = startCol; j < endCol; j++){
if(flg != grid[i][j]){
return new Node(false, false, getQuad(grid, startRow, startCol, midRow, midCol), getQuad(grid, startRow, midCol, midRow, endCol), getQuad(grid, midRow, startCol, endRow, midCol), getQuad(grid, midRow, midCol, endRow, endCol));
}
}
}
return new Node(flg, true, NULL, NULL, NULL, NULL);
}
};
