四叉树,按照定义递归求解
其中sum的计算可以使用二维前缀和来优化
ref{:target=”_blank”}
C++ 代码
/*
// Definition for a QuadTree node.
class Node {
public:
bool val;
bool isLeaf;
Node* topLeft;
Node* topRight;
Node* bottomLeft;
Node* bottomRight;
Node() {
val = false;
isLeaf = false;
topLeft = NULL;
topRight = NULL;
bottomLeft = NULL;
bottomRight = NULL;
}
Node(bool _val, bool _isLeaf) {
val = _val;
isLeaf = _isLeaf;
topLeft = NULL;
topRight = NULL;
bottomLeft = NULL;
bottomRight = NULL;
}
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 n = grid.size();
return dfs(grid, 0, 0, n-1, n-1);
}
Node* dfs(vector<vector<int>>& grid, int i, int j, int x, int y) {
if(i==x){
return new Node(grid[i][j], true);
}
int len = x - i + 1;
int sum = 0;
for(int a = i; a<=x; ++a) {
for(int b=j; b<=y; ++b) {
sum += grid[a][b];
}
}
if(sum == 0 or sum == len*len) {
return new Node(grid[i][j], true);
}
// 四叉树
Node* root = new Node(1, false);
int child_len = len/2;
root->topLeft = dfs(grid, i, j, i+child_len-1, j+child_len-1);
root->topRight = dfs(grid, i, j+child_len, i+child_len-1, y);
root->bottomLeft = dfs(grid, i+child_len, j, x, j+child_len-1);
root->bottomRight = dfs(grid, i+child_len, j+child_len, x, y);
return root;
}
};