友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
558. 四叉树交集
二进制矩阵中的所有元素不是 0 就是 1。
给你两个四叉树，quadTree1 和 quadTree2。其中 quadTree1 表示一个 n * n 二进制矩阵，而 quadTree2 表示另一个 n * n 二进制矩阵。
请你返回一个表示 n * n 二进制矩阵的四叉树，它是 quadTree1 和 quadTree2 所表示的两个二进制矩阵进行 按位逻辑或运算 的结果。
注意，当 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;
}
我们可以按以下步骤为二维区域构建四叉树：
-
如果当前网格的值相同（即，全为
0或者全为1），将isLeaf设为 True ，将val设为网格相应的值，并将四个子节点都设为 Null 然后停止。 -
如果当前网格的值不同，将
isLeaf设为 False， 将val设为任意值，然后如下图所示，将当前网格划分为四个子网格。 -
使用适当的子网格递归每个子节点。
如果你想了解更多关于四叉树的内容，可以参考 百科。
四叉树格式：
输出为使用层序遍历后四叉树的序列化形式，其中 null 表示路径终止符，其下面不存在节点。
它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val]。
如果 isLeaf 或者 val 的值为 True，则表示它在列表 [isLeaf, val] 中的值为 1 ；如果 isLeaf 或者 val 的值为 False，则表示值为 0 。
示例 1：
输入：quadTree1 = [[0,1],[1,1],[1,1],[1,0],[1,0]] , quadTree2 = [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]] 输出：[[0,0],[1,1],[1,1],[1,1],[1,0]] 解释：quadTree1 和 quadTree2 如上所示。由四叉树所表示的二进制矩阵也已经给出。 如果我们对这两个矩阵进行按位逻辑或运算，则可以得到下面的二进制矩阵，由一个作为结果的四叉树表示。 注意，我们展示的二进制矩阵仅仅是为了更好地说明题意，你无需构造二进制矩阵来获得结果四叉树。
示例 2：
输入：quadTree1 = [[1,0]] , quadTree2 = [[1,0]] 输出：[[1,0]] 解释：两个数所表示的矩阵大小都为 1*1，值全为 0 结果矩阵大小为 1*1，值全为 0 。
提示：
-
quadTree1和quadTree2都是符合题目要求的四叉树，每个都代表一个n * n的矩阵。 -
n == 2x，其中0 <= x <= 9.
思路分析
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-03-14 21:48:07
*/
public Node intersect(Node quadTree1, Node quadTree2) {
if (quadTree1.isLeaf) {
if (quadTree1.val) {
return new Node(true, true);
} else {
return new Node(quadTree2.val, quadTree2.isLeaf, quadTree2.topLeft,
quadTree2.topRight, quadTree2.bottomLeft, quadTree2.bottomRight);
}
}
if (quadTree2.isLeaf) {
// 妙啊！减少了重复代码！
return intersect(quadTree2, quadTree1);
}
Node topLeft = intersect(quadTree1.topLeft, quadTree2.topLeft);
Node topRight = intersect(quadTree1.topRight, quadTree2.topRight);
Node bottomLeft = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
Node bottomRight = intersect(quadTree1.bottomRight, quadTree2.bottomRight);
if (topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf
&& topLeft.val == topRight.val && topRight.val == bottomLeft.val && bottomLeft.val == bottomRight.val) {
return new Node(true, true);
}
return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
}