Description#
Given a n * n
matrix grid
of 0's
and 1's
only. We want to represent grid
with a Quad-Tree.
Return the root of the Quad-Tree representing grid
.
A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:
val
: True if the node represents a grid of 1's or False if the node represents a grid of 0's. Notice that you can assign the val
to True or False when isLeaf
is False, and both are accepted in the answer.isLeaf
: True if the node is a leaf node on the tree or False if the node has four children.
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
}
We can construct a Quad-Tree from a two-dimensional area using the following steps:
- If the current grid has the same value (i.e all
1's
or all 0's
) set isLeaf
True and set val
to the value of the grid and set the four children to Null and stop. - If the current grid has different values, set
isLeaf
to False and set val
to any value and divide the current grid into four sub-grids as shown in the photo. - Recurse for each of the children with the proper sub-grid.
![](https://spcdn.pages.dev/leetcode/problems/0427.Construct%20Quad%20Tree/images/new_top.png)
If you want to know more about the Quad-Tree, you can refer to the wiki.
Quad-Tree format:
You don't need to read this section for solving the problem. This is only if you want to understand the output format here. The output represents the serialized format of a Quad-Tree using level order traversal, where null
signifies a path terminator where no node exists below.
It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list [isLeaf, val]
.
If the value of isLeaf
or val
is True we represent it as 1 in the list [isLeaf, val]
and if the value of isLeaf
or val
is False we represent it as 0.
Example 1:
![](https://spcdn.pages.dev/leetcode/problems/0427.Construct%20Quad%20Tree/images/grid1.png)
Input: grid = [[0,1],[1,0]]
Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Explanation: The explanation of this example is shown below:
Notice that 0 represents False and 1 represents True in the photo representing the Quad-Tree.
Example 2:
![](https://spcdn.pages.dev/leetcode/problems/0427.Construct%20Quad%20Tree/images/e2mat.png)
Input: grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
Output: [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
Explanation: All values in the grid are not the same. We divide the grid into four sub-grids.
The topLeft, bottomLeft and bottomRight each has the same value.
The topRight have different values so we divide it into 4 sub-grids where each has the same value.
Explanation is shown in the photo below:
Constraints:
n == grid.length == grid[i].length
n == 2x
where 0 <= x <= 6
Solutions#
Solution 1#
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
| """
# Definition for a QuadTree node.
class Node:
def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
self.val = val
self.isLeaf = isLeaf
self.topLeft = topLeft
self.topRight = topRight
self.bottomLeft = bottomLeft
self.bottomRight = bottomRight
"""
class Solution:
def construct(self, grid: List[List[int]]) -> 'Node':
def dfs(a, b, c, d):
zero = one = 0
for i in range(a, c + 1):
for j in range(b, d + 1):
if grid[i][j] == 0:
zero = 1
else:
one = 1
isLeaf = zero + one == 1
val = isLeaf and one
if isLeaf:
return Node(grid[a][b], True)
topLeft = dfs(a, b, (a + c) // 2, (b + d) // 2)
topRight = dfs(a, (b + d) // 2 + 1, (a + c) // 2, d)
bottomLeft = dfs((a + c) // 2 + 1, b, c, (b + d) // 2)
bottomRight = dfs((a + c) // 2 + 1, (b + d) // 2 + 1, c, d)
return Node(val, isLeaf, topLeft, topRight, bottomLeft, bottomRight)
return dfs(0, 0, len(grid) - 1, len(grid[0]) - 1)
|
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
| /*
// Definition for a QuadTree node.
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
public Node() {
this.val = false;
this.isLeaf = false;
this.topLeft = null;
this.topRight = null;
this.bottomLeft = null;
this.bottomRight = null;
}
public Node(boolean val, boolean isLeaf) {
this.val = val;
this.isLeaf = isLeaf;
this.topLeft = null;
this.topRight = null;
this.bottomLeft = null;
this.bottomRight = null;
}
public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node
bottomRight) { this.val = val; this.isLeaf = isLeaf; this.topLeft = topLeft; this.topRight =
topRight; this.bottomLeft = bottomLeft; this.bottomRight = bottomRight;
}
};
*/
class Solution {
public Node construct(int[][] grid) {
return dfs(0, 0, grid.length - 1, grid[0].length - 1, grid);
}
private Node dfs(int a, int b, int c, int d, int[][] grid) {
int zero = 0, one = 0;
for (int i = a; i <= c; ++i) {
for (int j = b; j <= d; ++j) {
if (grid[i][j] == 0) {
zero = 1;
} else {
one = 1;
}
}
}
boolean isLeaf = zero + one == 1;
boolean val = isLeaf && one == 1;
Node node = new Node(val, isLeaf);
if (isLeaf) {
return node;
}
node.topLeft = dfs(a, b, (a + c) / 2, (b + d) / 2, grid);
node.topRight = dfs(a, (b + d) / 2 + 1, (a + c) / 2, d, grid);
node.bottomLeft = dfs((a + c) / 2 + 1, b, c, (b + d) / 2, grid);
node.bottomRight = dfs((a + c) / 2 + 1, (b + d) / 2 + 1, c, d, grid);
return node;
}
}
|
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
| /*
// 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) {
return dfs(0, 0, grid.size() - 1, grid[0].size() - 1, grid);
}
Node* dfs(int a, int b, int c, int d, vector<vector<int>>& grid) {
int zero = 0, one = 0;
for (int i = a; i <= c; ++i) {
for (int j = b; j <= d; ++j) {
if (grid[i][j])
one = 1;
else
zero = 1;
}
}
bool isLeaf = zero + one == 1;
bool val = isLeaf && one;
Node* node = new Node(val, isLeaf);
if (isLeaf) return node;
node->topLeft = dfs(a, b, (a + c) / 2, (b + d) / 2, grid);
node->topRight = dfs(a, (b + d) / 2 + 1, (a + c) / 2, d, grid);
node->bottomLeft = dfs((a + c) / 2 + 1, b, c, (b + d) / 2, grid);
node->bottomRight = dfs((a + c) / 2 + 1, (b + d) / 2 + 1, c, d, grid);
return node;
}
};
|
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
| /**
* Definition for a QuadTree node.
* type Node struct {
* Val bool
* IsLeaf bool
* TopLeft *Node
* TopRight *Node
* BottomLeft *Node
* BottomRight *Node
* }
*/
func construct(grid [][]int) *Node {
var dfs func(a, b, c, d int) *Node
dfs = func(a, b, c, d int) *Node {
zero, one := 0, 0
for i := a; i <= c; i++ {
for j := b; j <= d; j++ {
if grid[i][j] == 0 {
zero = 1
} else {
one = 1
}
}
}
isLeaf := zero+one == 1
val := isLeaf && one == 1
node := &Node{Val: val, IsLeaf: isLeaf}
if isLeaf {
return node
}
node.TopLeft = dfs(a, b, (a+c)/2, (b+d)/2)
node.TopRight = dfs(a, (b+d)/2+1, (a+c)/2, d)
node.BottomLeft = dfs((a+c)/2+1, b, c, (b+d)/2)
node.BottomRight = dfs((a+c)/2+1, (b+d)/2+1, c, d)
return node
}
return dfs(0, 0, len(grid)-1, len(grid[0])-1)
}
|