本文首发于馆主君晓的博客，04-29每日一题
题目描述
??题目链接，427. 建立四叉树，题目截图如下：
题目分析
??这个题目的意思就是，给你一个二维数组，让你构建一个四叉树，规矩是这样的，我们的二维数组是nxn大小的，并且n最小为1，最大为64。在二维数组中，我们将数组划分成四个部分，如下图所示，如果某个区域，比如说topLeft这个区域的数值全部相等，那么我们就说topLeft这个结点为叶子结点。如果topLeft这个区域里的数值不相等，那么我们就将其再划分成四个区域，再去判断。
??听完上面的分析之后，是不是觉得这个题目用递归来做呢？Bingo！我们的思路就是递归，首先给我们一个二维数组，我们递归构建四叉树的四个子节点。话不多说，看下面的代码就懂了，时候不早了，收工睡觉！
代码实现
??c++代码实现如下：
/*
// 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) {
function<Node*(int,int,int,int)> dfs = [&](int r0,int c0,int r1,int c1){
for(int i = r0;i<r1;i++){
for(int j = c0;j<c1;j++){
if(grid[i][j]!=grid[r0][c0]){
// 存在不相等的值 则不是叶子节点
return new Node(true,false,
dfs(r0,c0,(r0+r1)/2,(c0+c1)/2),
dfs(r0,(c0+c1)/2,(r0+r1)/2,c1),
dfs((r0+r1)/2,c0,r1,(c0+c1)/2),
dfs((r0+r1)/2,(c0+c1)/2,r1,c1));
}
}
}
// 该节点是叶子节点
return new Node(grid[r0][c0],true);
};
return dfs(0,0,grid.size(),grid.size());
}
};
结语
??凛然少年气！
