Powered By GitBook
427.Construct Quad Tree

427.Construct Quad Tree

难度:Easy
我们想要使用一棵四叉树来储存一个 N x N 的布尔值网络。网络中每一格的值只会是真或假。树的根结点代表整个网络。对于每个结点, 它将被分等成四个孩子结点直到这个区域内的值都是相同的.
每个结点还有另外两个布尔变量: isLeaf 和 val。isLeaf 当这个节点是一个叶子结点时为真。val 变量储存叶子结点所代表的区域的值。
你的任务是使用一个四叉树表示给定的网络。下面的例子将有助于你理解这个问题:
给定下面这个8 x 8 网络,我们将这样建立一个对应的四叉树:
由上文的定义,它能被这样分割:
对应的四叉树应该像下面这样,每个结点由一对 (isLeaf, val) 所代表.
对于非叶子结点,val 可以是任意的,所以使用 * 代替。
提示:
N 将小于 1000 且确保是 2 的整次幂。 如果你想了解更多关于四叉树的知识,你可以参考这个wiki页面。
递归建立,判断和来确定是否全0或全1.
1
/*
2
// Definition for a QuadTree node.
3
class Node {
4
public:
5
bool val;
6
bool isLeaf;
7
Node* topLeft;
8
Node* topRight;
9
Node* bottomLeft;
10
Node* bottomRight;
11
12
Node() {}
13
14
Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
15
val = _val;
16
isLeaf = _isLeaf;
17
topLeft = _topLeft;
18
topRight = _topRight;
19
bottomLeft = _bottomLeft;
20
bottomRight = _bottomRight;
21
}
22
};
23
*/
24
class Solution {
25
public:
26
Node* construct(vector<vector<int>>& grid) {
27
int N=grid.size();
28
if(N==0) return NULL;
29
int sum =0;
30
for(auto r:grid)
31
for(auto c: r)
32
sum +=c;
33
// cout<<sum<<endl;
34
if( sum== N*N || sum ==0)
35
{
36
return new Node(grid[0][0],true, NULL,NULL,NULL,NULL);
37
}
38
39
vector<vector<int>> tl(N/2,vector<int>(N/2,0));
40
vector<vector<int>> tr(N/2,vector<int>(N/2,0));
41
vector<vector<int>> bl(N/2,vector<int>(N/2,0));
42
vector<vector<int>> br(N/2,vector<int>(N/2,0));
43
bool ftl, ftr,fbl, fbr;
44
for(int i=0;i<N/2;i++)
45
for(int j=0;j<N/2;j++)
46
{
47
tl[i][j]=grid[i][j];
48
bl[i][j]=grid[i+N/2][j];
49
tr[i][j]=grid[i][j+N/2];
50
br[i][j]=grid[i+N/2][j+N/2];
51
}
52
53
return new Node(false,false,construct(tl),construct(tr),construct(bl),construct(br));
54
}
55
};
Copied!
Last modified 2yr ago
Copy link