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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| #include <stddef.h>
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;
}
};
#include <vector>
#include <climits>
#include <stddef.h>
using std::vector;
class Solution {
private:
Node *buildQuadTree(vector<vector<int> > &grid, int si, int sj, int size)
{
int i, j;
int val = grid[si][sj];
bool is_leaf = true;
for (i = si; i < si + size; i++) {
for (j = sj; j < sj + size; j++) {
if (grid[i][j] != val) {
is_leaf = false;
break;
}
}
}
Node *root = new Node;
if (is_leaf) {
root->topLeft = NULL;
root->topRight = NULL;
root->bottomLeft = NULL;
root->bottomRight = NULL;
root->val = val;
} else {
root->topLeft = buildQuadTree(grid, si, sj, size / 2);
root->topRight = buildQuadTree(grid, si, sj + size / 2, size / 2);
root->bottomLeft = buildQuadTree(grid, si + size / 2, sj, size / 2);
root->bottomRight = buildQuadTree(grid, si + size / 2, sj + size / 2, size / 2);
root->val = INT_MAX;
}
root->isLeaf = is_leaf;
return root;
}
public:
Node *construct(vector<vector<int> > &grid)
{
int i, j, n = grid.size();
return buildQuadTree(grid, 0, 0, n);
}
};
|
