LeetCode每日一题——427. 建立四叉树

简介: 给你一个 n * n 矩阵 grid ,矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。

题目

给你一个 n * n 矩阵 grid ,矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。

你需要返回能表示矩阵的 四叉树 的根结点。

注意,当 isLeaf 为 False 时,你可以把 True 或者 False 赋值给节点,两种值都会被判题机制 接受 。

四叉树数据结构中,每个内部节点只有四个子节点。此外,每个节点都有两个属性:

val:储存叶子结点所代表的区域的值。1 对应 True,0 对应 False;

isLeaf: 当这个节点是一个叶子结点时为 True,如果它有 4 个子节点则为 False 。

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

我们可以按以下步骤为二维区域构建四叉树:

1、如果当前网格的值相同(即,全为 0 或者全为 1),将 isLeaf 设为 True ,将 val 设为网格相应的值,并将四个子节点都设为 Null 然后停止。

2、如果当前网格的值不同,将 isLeaf 设为 False, 将 val 设为任意值,然后如下图所示,将当前网格划分为四个子网格。

3、使用适当的子网格递归每个子节点。

2345_image_file_copy_61.jpg

四叉树格式:

输出为使用层序遍历后四叉树的序列化形式,其中 null 表示路径终止符,其下面不存在节点。

它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val] 。

如果 isLeaf 或者 val 的值为 True ,则表示它在列表 [isLeaf, val] 中的值为 1 ;如果 isLeaf 或者 val 的值为 False ,则表示值为 0 。

示例

示例 1:

2345_image_file_copy_62.jpg

输入:grid = [[0,1],[1,0]]

输出:[[0,1],[1,0],[1,1],[1,1],[1,0]]

解释:此示例的解释如下: 请注意,在下面四叉树的图示中,0 表示 false,1 表示 True 。

2345_image_file_copy_63.jpg

示例 2:

2345_image_file_copy_64.jpg

输入:grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]

输出:[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]

解释:网格中的所有值都不相同。我们将网格划分为四个子网格。 topLeft,bottomLeft 和 bottomRight均具有相同的值。 topRight 具有不同的值,因此我们将其再分为 4 个子网格,这样每个子网格都具有相同的值。 解释如下图所示:

2345_image_file_copy_65.jpg

示例 3:

输入:grid = [[1,1],[1,1]]

输出:[[1,1]]

示例 4:

输入:grid = [[0]]

输出:[[1,0]]

示例 5:

输入:grid = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]

输出:[[0,1],[1,1],[1,0],[1,0],[1,1]]

思路

又是看不懂题目的一天。。。。。

大致题意应该为,将一个大区域划分为若干个小区域(要求每个小区域中的val全部一致),每次都是将一个大区域划分为4份(直到小区域val全部一致,终止)。

使用深度优先遍历,调用函数dfs(r0: int, c0: int, r1: int, c1: int)从左至右分别是该格子的上侧行边界、左侧列边界、下册行边界,右侧列边界,首先判断当前格子中是否所有元素都等于左上角第一个元素, 如果相等直接返回Node(grid[r0][c0] == 1, True), 否则将该格子分别分为上下左右四个位置递归调用,具体边界分别为:

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),

题解

"""
# Definition for a QuadTree node.
class Node:
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight
"""
class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        def dfs(r0: int, c0: int, r1: int, c1: int) -> 'Node':
        # 直接返回
            if all(grid[i][j] == grid[r0][c0] for i in range(r0, r1) for j in range(c0, c1)):
                return Node(grid[r0][c0] == 1, True)
             # 分上下左右四个边界递归进行
            return 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 dfs(0, 0, len(grid), len(grid))
目录
相关文章
|
Go
golang力扣leetcode 427.建立四叉树
golang力扣leetcode 427.建立四叉树
104 0
|
机器学习/深度学习 算法
LeetCode——427. 建立四叉树
LeetCode——427. 建立四叉树
144 0
LeetCode——427. 建立四叉树
|
机器学习/深度学习
LeetCode每日一题(13)——建立四叉树(递归)
建立四叉树 1.题目 2.示例 3.思路 4.代码
220 0
LeetCode每日一题(13)——建立四叉树(递归)
|
机器学习/深度学习
leetcode-每日一题558. 四叉树交集(分治递归)
时间复杂度:O(n2),其中 n 是四叉树 quadTree1 和 quadTree2 对应矩阵的边长。最坏的情况下,整个矩阵都会被遍历
159 0
leetcode-每日一题558. 四叉树交集(分治递归)
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
186 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
138 6
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
303 2
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
199 3
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
10月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
246 1
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
260 7

热门文章

最新文章