LeetCode 427. 建立四叉树（递归）

Michael阿明

发布于 2020-07-13 16:02:22

5310

发布于 2020-07-13 16:02:22

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

1. 题目

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

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

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

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

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

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

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

提示： N 将小于 1000 且确保是 2 的整次幂。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/construct-quad-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 递归建树

// Definition for a QuadTree node.
class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;

    Node() {}

    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 {
    Node* r;
public:
    Node* construct(vector<vector<int>>& grid) {
        int m = grid.size();
        r = build(grid,0,0,m-1,m-1);
        return r;
    }

    Node* build(vector<vector<int>>& grid, int sx, int sy, int ex, int ey) {
        if(sx == ex || sy == ey)//只有1个单元了，不能划分了
            return new Node(grid[sx][sy],true,0,0,0,0);
        int mx = (sx+ex)/2, my = (sy+ey)/2;
        Node *root = new Node(true,true,0,0,0,0);//默认是叶子节点，val值是1
        int b1, b2, b3, b4;//是全1？全0？两种都有？
        b1 = judge(grid,sx,sy,mx,my);
        b2 = judge(grid,sx,my+1,mx,ey);
        b3 = judge(grid,mx+1,sy,ex,my);
        b4 = judge(grid,mx+1,my+1,ex,ey);
        if(b1==1 && b2==1 && b3==1 && b4==1)
        {	//全1
            return root;
        }
        else if(b1==0 && b2==0 && b3==0 && b4==0)
        {	//全0
            root->val = false;
            return root;
        }
        else
        {	//0,1都有
            root->isLeaf = false;
            root->topLeft = build(grid,sx,sy,mx,my);
            root->topRight = build(grid,sx,my+1,mx,ey);
            root->bottomLeft = build(grid,mx+1,sy,ex,my);
            root->bottomRight = build(grid,mx+1,my+1,ex,ey);
            return root;
        }
    }

    int judge(vector<vector<int>>& grid, int sx, int sy, int ex, int ey)
    {
        int i, j;
        bool allone = 1, allzero = 1;
        for(i = sx; i <= ex; ++i)
            for(j = sy; j <= ey; ++j)
                if(grid[i][j] == 0)
                {
                    allone = false;
                }
                else
                {
                    allzero = false;
                }
        if(allone^allzero)//全0或者全1
        {
            if(allone)
                return 1;//全1
            if(allzero)
                return 0;//全0
        }
        return -1;//0,1都有
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

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

编程算法

本文分享自作者个人站点/博客前往查看

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

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

编程算法

登录后参与评论

0 条评论

热度