05 August 2008
给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。
你需要返回能表示矩阵的 四叉树 的根结点。
注意，当 isLeaf 为 False 时，你可以把 True 或者 False 赋值给节点，两种值都会被判题机制 接受 。
四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性：
val：储存叶子结点所代表的区域的值。1 对应 True，0 对应 False；
isLeaf: 当这个节点是一个叶子结点时为 True，如果它有 4 个子节点则为 False 。
class Node { public boolean val; public boolean isLeaf; public Node topLeft; public Node topRight; public Node bottomLeft; public Node bottomRight; }
To do this recusively, we have to split the grid into 4 smaller sub-grids until the sub-grid’s length is 1. The sub-grid whose length is 1 is the leaf node.
We merge the sub-grids if all four sub-grids are leaf nodes and have same value.
Time Complexity: O(N^2), N is the length of the grid.
Space Complexity: O(N^2)
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 helper(grid, 0, 0, grid.length);
}
private Node helper(int[][] grid, int x, int y, int len) {
if (len == 1) {
return new Node(grid[x][y] != 0, true, null, null, null, null);
}
Node result = new Node();
Node topLeft = helper(grid, x, y, len / 2);
Node topRight = helper(grid, x, y + len / 2, len / 2);
Node bottomLeft = helper(grid, x + len / 2, y, len / 2);
Node bottomRight = helper(grid, x + len / 2, y + len / 2, len / 2);
if (topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf
&& topLeft.val == topRight.val && topRight.val == bottomLeft.val && bottomLeft.val == bottomRight.val) {
result.isLeaf = true;
result.val = topLeft.val;
} else {
result.topLeft = topLeft;
result.topRight = topRight;
result.bottomLeft = bottomLeft;
result.bottomRight = bottomRight;
}
return result;
}
}
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
class Solution {
public Node construct(int[][] grid) {
int n = grid.length;
if (n == 0) return null;
Node[][] pre = new Node[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
pre[i][j] = new Node();
pre[i][j].val = grid[i][j] == 1;
pre[i][j].isLeaf = true;
}
}
while (n > 1) {
n /= 2;
Node[][] cur = new Node[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int x = 2 * i, y = 2 * j;
boolean tag = pre[x][y].val;
if (pre[x][y].isLeaf && pre[x + 1][y].isLeaf
&& pre[x][y + 1].isLeaf && pre[x + 1][y + 1].isLeaf
&& pre[x + 1][y].val == tag && pre[x][y + 1].val == tag
&& pre[x + 1][y + 1].val == tag) {
cur[i][j] = new Node();
cur[i][j].val = tag;
cur[i][j].isLeaf = true;
} else {
cur[i][j] =
new Node(true, false, pre[x][y], pre[x][y + 1],
pre[x + 1][y], pre[x + 1][y + 1]);
}
}
}
pre = cur;
}
return pre[0][0];
}
}