对不起，对不起，来迟了，今天的每日一题有点绕

题目描述

  题目链接，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());
    }
};

结语

  凛然少年气！

Q.E.D.