LeetCode刷题实战427：建立四叉树

程序员小猿

发布于 2021-11-04 11:00:29

29600

代码可运行

文章被收录于专栏：程序IT圈程序IT圈

运行总次数：0

代码可运行

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 建立四叉树，我们先来看题面：

https://leetcode-cn.com/problems/construct-quad-tree/

示例

解题

https://blog.csdn.net/zrh_CSDN/article/details/84140253

解题思路：

我们想要使用一棵四叉树来储存一个 N x N 的布尔值网络。网络中每一格的值只会是真或假。树的根结点代表整个网络。对于每个结点, 它将被分等成四个孩子结点直到这个区域内的值都是相同的。

每个结点还有另外两个布尔变量: isLeaf 和 val。isLeaf 当这个节点是一个叶子结点时为真。val 变量储存叶子结点所代表的区域的值。

你的任务是使用一个四叉树表示给定的网络。下面的例子将有助于你理解这个问题：

给定下面这个8 x 8 网络，我们将这样建立一个对应的四叉树：

由上文的定义，它能被这样分割：

对应的四叉树应该像下面这样，每个结点由一对 (isLeaf, val) 所代表.

对于非叶子结点，val 可以是任意的，所以使用*代替。

提示：

N 将小于 1000 且确保是 2 的整次幂。
如果你想了解更多关于四叉树的知识，你可以参考这个 wiki 页面。

class Solution {
public:
    Node* construct(vector<vector<int>>& grid) {
        int m = grid.size();
        // cout<<m<<endl;
        if(m == 0){
            return NULL;
        }else if(m == 1){
            if(grid[0][0] == 1){
                return new Node(true, true, NULL, NULL, NULL, NULL);
            }else{
                return new Node(false, true, NULL, NULL, NULL, NULL);
            }
        }else{
            vector<vector<int>> lt; // left top
            vector<vector<int>> rt; // right top
            vector<vector<int>> lb; // left bottom
            vector<vector<int>> rb; //right bottom
            int half = m/2;
            for(int i = 0; i < half; i++){
                lt.push_back(vector<int>(grid[i].begin(), grid[i].begin() + half));
                lb.push_back(vector<int>(grid[i+half].begin(), grid[i+half].begin() + half));
                rt.push_back(vector<int>(grid[i].begin()+half, grid[i].end()));
                rb.push_back(vector<int>(grid[i+half].begin()+half, grid[i+half].end()));
            }
            Node* _lt = construct(lt);
            Node* _rt = construct(rt);
            Node* _lb = construct(lb);
            Node* _rb = construct(rb);
            if(_lt->isLeaf && _rt->isLeaf && _lb->isLeaf && _rb->isLeaf){
                if(_lt->val && _rt->val && _lb->val && _rb->val){
                    return new Node(true, true, NULL, NULL, NULL, NULL);
                }else if(!_lt->val && !_rt->val && !_lb->val && !_rb->val){
                    return new Node(false, true, NULL, NULL, NULL, NULL);
                }else{
                    return new Node(false, false, _lt, _rt, _lb, _rb);
                }
            }else{
                return new Node(false, false, _lt, _rt, _lb, _rb);
            }
        }
    }
};

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-11-02，如有侵权请联系 cloudcommunity@tencent.com 删除

https

网络安全

编程算法

本文分享自程序员小猿微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

https

网络安全

编程算法

登录后参与评论

0 条评论

热度