【04-29】力扣每日一题

本文首发于馆主君晓的博客，04-29每日一题

  题目链接，427. 建立四叉树，题目截图如下：

  这个题目的意思就是，给你一个二维数组，让你构建一个四叉树，规矩是这样的，我们的二维数组是nxn大小的，并且n最小为1，最大为64。在二维数组中，我们将数组划分成四个部分，如下图所示，如果某个区域，比如说topLeft这个区域的数值全部相等，那么我们就说topLeft这个结点为叶子结点。如果topLeft这个区域里的数值不相等，那么我们就将其再划分成四个区域，再去判断。

  听完上面的分析之后，是不是觉得这个题目用递归来做呢？Bingo！我们的思路就是递归，首先给我们一个二维数组，我们递归构建四叉树的四个子节点。话不多说，看下面的代码就懂了，时候不早了，收工睡觉！

  c++代码实现如下：

class Solution {
public:
    Node* construct(vector>& grid) {
        function dfs = [&](int r0,int c0,int r1,int c1){
            for(int i = r0;i
                for(int j = c0;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());
    }
};

  凛然少年气！