[数据结构与算法](2022.04.29)力扣每日一题 - dfs

前言

今天开始用C++刷题的第一天，以后刷题尽量使用C++作为主要的刷题工具，主要目标是熟练使用stl的特性，加快以后的刷题速度，正好今天也是我不熟悉的一个领域，图论，所以这赶紧刷一刷。今天是dfs的内容，大家一起卷起来。

每日一题

链接：427. 建立四叉树

具体数据结构：

class Node {
public boolean val;
  public boolean isLeaf;
  public Node topLeft;
  public Node topRight;
  public Node bottomLeft;
  public Node bottomRight;
}

算法思路

1. 对于这个问题，我们只要深度优先遍历，找到1x1的格子就是最终的叶子节点，创建节点进行返回就ok
2. 对于非叶子节点，我们需要判断它的四个孩子是否满足全是叶子节点且值相同，满足我们就将四个孩子设置为null，然后设置当前节点为叶子节点。
3. 所有结果处理完成就是根节点的返回。

代码分析

补充知识点：构造函数

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 {
    bool AllSame(Node * node){
        Node *tmp[4] = {node->topLeft,node->topRight,node->bottomLeft,node->bottomRight};
         //判断是否都是叶子节点
        for(int i = 0;i < 4;++i)   
            if(!tmp[i]->isLeaf) return false;
        //判断值是否相同
        for(int i = 1;i < 4;++i)    
            if(tmp[i]->val != tmp[i - 1]->val) return false;
        //严谨一点 归还内存
        for(int i = 0;i < 4;++i)
            delete(tmp[i]);
        return true;
    }
    Node *dfs(vector<vector<int>> & grid, int row_start, int col_start,int len){
        if(len == 1){
            return new Node(grid[row_start][col_start], true);
        }
        int mid = len / 2;  //长度为之前的一半
        //直接根据规则创建对应的节点
        Node *node = new Node(grid[row_start][col_start], false, 
                            dfs(grid, row_start,        col_start,         mid), 
                            dfs(grid, row_start,        col_start + mid,   mid),
                            dfs(grid, row_start + mid,  col_start,         mid),
                            dfs(grid, row_start + mid,  col_start + mid,   mid));
        //如果需要合并就进行合并
        if(AllSame(node)){
            node->topLeft = node->topRight = node->bottomLeft = node->bottomRight = NULL;
            node->isLeaf = true;
        }
        return node;
    }

public:
    Node* construct(vector<vector<int>>& grid) {
        int n = grid.size();
        return dfs(grid, 0, 0, n);
    }
};

注意的点

1. 其实该有的注释我都写了
2. 我就算不是双百我也要delete 不回收对于底层开发来说非常的致命，一定要注意！！！！！

写在最后

今天是C++刷题第一天，大家一起努力，我的小水墨屏快要做完了，加油呀！！！

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖