-
Notifications
You must be signed in to change notification settings - Fork 0
/
0427-construct-quad-tree.cpp
70 lines (62 loc) · 2.14 KB
/
0427-construct-quad-tree.cpp
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
/*
// 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* solve(vector<vector<int>>& grid, int x1, int y1, int length) {
// Return a leaf node if the matrix size is one.
if (length == 1) {
return new Node(grid[x1][y1], true);
}
// Recursive calls to the four sub-matrices.
Node* topLeft = solve(grid, x1, y1, length / 2);
Node* topRight = solve(grid, x1, y1 + length / 2, length / 2);
Node* bottomLeft = solve(grid, x1 + length / 2, y1, length / 2);
Node* bottomRight = solve(grid, x1 + length / 2, y1 + length / 2, length / 2);
// If the four returned nodes are leaf and have the same values
// Return a leaf node with the same value.
if (topLeft -> isLeaf && topRight -> isLeaf && bottomLeft -> isLeaf && bottomRight -> isLeaf
&& topLeft -> val == topRight -> val && topRight -> val == bottomLeft -> val
&& bottomLeft -> val == bottomRight -> val) {
return new Node(topLeft -> val, true);
}
// If the four nodes aren't identical, return non-leaf node with corresponding child pointers.
return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
}
Node* construct(vector<vector<int>>& grid) {
return solve(grid, 0, 0, grid.size());
}
};