LeetCode 题解工作台
建立四叉树
给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。 你需要返回能表示矩阵 grid 的 四叉树 的根结点。 四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性： val ：储存叶子结点所代表的区域的值。1 对应 True …
4
题型
4
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
DFS 递归遍历 grid，先判断 grid 是否为叶子节点，是则返回叶子节点相关信息；否则递归 grid 4 个子节点。 """
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。
你需要返回能表示矩阵 grid 的 四叉树 的根结点。
四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性：
val：储存叶子结点所代表的区域的值。1 对应 True，0 对应 False。注意，当isLeaf为 False 时，你可以把 True 或者 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;
}
我们可以按以下步骤为二维区域构建四叉树：
- 如果当前网格的值相同（即，全为
0或者全为1），将isLeaf设为 True ，将val设为网格相应的值，并将四个子节点都设为 Null 然后停止。 - 如果当前网格的值不同，将
isLeaf设为 False， 将val设为任意值，然后如下图所示，将当前网格划分为四个子网格。 - 使用适当的子网格递归每个子节点。
如果你想了解更多关于四叉树的内容，可以参考 百科 。
四叉树格式：
你不需要阅读本节来解决这个问题。只有当你想了解输出格式时才会这样做。输出为使用层序遍历后四叉树的序列化形式，其中 null 表示路径终止符，其下面不存在节点。
它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val] 。
如果 isLeaf 或者 val 的值为 True ，则表示它在列表 [isLeaf, val] 中的值为 1 ；如果 isLeaf 或者 val 的值为 False ，则表示值为 0 。
示例 1：
输入：grid = [[0,1],[1,0]] 输出：[[0,1],[1,0],[1,1],[1,1],[1,0]] 解释：此示例的解释如下： 请注意，在下面四叉树的图示中，0 表示 false，1 表示 True 。
示例 2：
输入：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 个子网格，这样每个子网格都具有相同的值。 解释如下图所示：
提示：
n == grid.length == grid[i].lengthn == 2x其中0 <= x <= 6
解题思路
方法一：DFS
DFS 递归遍历 grid，先判断 grid 是否为叶子节点，是则返回叶子节点相关信息；否则递归 grid 4 个子节点。
"""
# 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(a, b, c, d):
zero = one = 0
for i in range(a, c + 1):
for j in range(b, d + 1):
if grid[i][j] == 0:
zero = 1
else:
one = 1
isLeaf = zero + one == 1
val = isLeaf and one
if isLeaf:
return Node(grid[a][b], True)
topLeft = dfs(a, b, (a + c) // 2, (b + d) // 2)
topRight = dfs(a, (b + d) // 2 + 1, (a + c) // 2, d)
bottomLeft = dfs((a + c) // 2 + 1, b, c, (b + d) // 2)
bottomRight = dfs((a + c) // 2 + 1, (b + d) // 2 + 1, c, d)
return Node(val, isLeaf, topLeft, topRight, bottomLeft, bottomRight)
return dfs(0, 0, len(grid) - 1, len(grid[0]) - 1)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of regions recursively subdivided; in the worst case it approaches O(n^2 log n) for maximum splits. Space complexity includes recursion stack and tree nodes, also roughly O(n^2) in the worst case. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect candidate to identify uniform sub-grids and avoid unnecessary recursion.
- question_mark
Look for proper recursive subdivision of the grid into four quadrants per internal node.
- question_mark
Assess if the candidate correctly maintains node attributes val and isLeaf throughout traversal.
常见陷阱
外企场景- error
Creating internal nodes for uniform regions instead of leaf nodes, increasing unnecessary tree size.
- error
Failing to divide the grid properly into exactly four quadrants for each non-leaf node.
- error
Ignoring tracking of uniform states leading to incorrect isLeaf assignments and wrong val values.
进阶变体
外企场景- arrow_right_alt
Construct Quad-Tree for larger matrices with varying sizes n = 2^x where 0 <= x <= 6.
- arrow_right_alt
Modify to compress sparse matrices where many 0's can be grouped to optimize space.
- arrow_right_alt
Extend to track additional metadata per node, such as counts of 1's and 0's, while maintaining traversal pattern.