Medium
题目描述
二进制矩阵是一个只包含 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，如果它有四个子节点则为False。
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
}
我们可以按以下步骤为二维区域构建四叉树：
- 如果当前网格的值相同（即，全为
1或者全为0），将isLeaf设为 True ，将val设为网格相应的值，并将四个子节点都设为 Null 然后停止。 - 如果当前网格的值不同，将
isLeaf设为 False， 将val设为任意值，然后如下图所示，将当前网格划分为四个子网格。 - 使用适当的子网格递归每个子节点。
示例 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 的矩阵，且值为 false 的四叉树
结果矩阵大小为 1*1，值为 false
提示：
quadTree1和quadTree2都是符合题目要求的四叉树，每个都代表一个n * n的矩阵。n == 2^x其中0 <= x <= 9。
解题思路
解题思路
这道题要求对两个四叉树表示的二进制矩阵进行逻辑或运算。我们可以使用递归分治的思想来解决这个问题。
核心思路
逻辑或运算的特点是：0 OR 0 = 0，0 OR 1 = 1，1 OR 0 = 1，1 OR 1 = 1。
对于四叉树节点，我们需要考虑以下几种情况：
- 两个节点都是叶子节点：直接对它们的值进行逻辑或运算
- 其中一个是叶子节点，另一个不是：
- 如果叶子节点的值为 1，则整个区域都是 1，结果是叶子节点值为 1
- 如果叶子节点的值为 0，则结果取决于另一个非叶子节点
- 两个节点都不是叶子节点：需要递归处理四个对应的子节点
优化策略
在递归构建结果树时，我们需要检查是否可以将四个子节点合并为一个叶子节点。如果四个子节点都是叶子节点且值相同，我们可以将它们合并。
算法步骤
- 处理基础情况：至少一个节点是叶子节点
- 递归处理四个子节点
- 检查是否可以合并子节点
- 构建并返回结果节点
推荐解法：递归分治法，时间复杂度最优且代码简洁。
代码实现
class Solution {
public:
Node* intersect(Node* quadTree1, Node* quadTree2) {
// 如果其中一个节点是叶子节点
if (quadTree1->isLeaf) {
// 如果quadTree1是1，则结果是1（1 OR anything = 1）
return quadTree1->val ? quadTree1 : quadTree2;
}
if (quadTree2->isLeaf) {
// 如果quadTree2是1，则结果是1（anything OR 1 = 1）
return quadTree2->val ? 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 &&
topLeft->val == bottomLeft->val &&
topLeft->val == bottomRight->val) {
return new Node(topLeft->val, true);
}
// 不能合并，创建内部节点
return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
}
};
class Solution:
def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':
# 如果其中一个节点是叶子节点
if quadTree1.isLeaf:
# 如果quadTree1是1，则结果是1（1 OR anything = 1）
return quadTree1 if quadTree1.val else quadTree2
if quadTree2.isLeaf:
# 如果quadTree2是1，则结果是1（anything OR 1 = 1）
return quadTree2 if quadTree2.val else quadTree1
# 两个都不是叶子节点，递归处理四个子节点
topLeft = self.intersect(quadTree1.topLeft, quadTree2.topLeft)
topRight = self.intersect(quadTree1.topRight, quadTree2.topRight)
bottomLeft = self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)
bottomRight = self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)
# 检查是否可以合并为一个叶子节点
if (topLeft.isLeaf and topRight.isLeaf and
bottomLeft.isLeaf and bottomRight.isLeaf and
topLeft.val == topRight.val == bottomLeft.val == bottomRight.val):
return Node(topLeft.val, True, None, None, None, None)
# 不能合并，创建内部节点
return Node(False, False, topLeft, topRight, bottomLeft, bottomRight)
public class Solution {
public Node Intersect(Node quadTree1, Node quadTree2) {
// 如果其中一个节点是叶子节点
if (quadTree1.isLeaf) {
// 如果quadTree1是1，则结果是1（1 OR anything = 1）
return quadTree1.val ? quadTree1 : quadTree2;
}
if (quadTree2.isLeaf) {
// 如果quadTree2是1，则结果是1（anything OR 1 = 1）
return quadTree2.val ? 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 &&
topLeft.val == bottomLeft.val &&
topLeft.val == bottomRight.val) {
return new Node(topLeft.val, true, null, null, null, null);
}
// 不能合并，创建内部节点
return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
}
}
var intersect = function(quadTree1, quadTree2) {
if (quadTree1.isLeaf) {
if (quadTree1.val) {
return quadTree1;
} else {
return quadTree2;
}
}
if (quadTree2.isLeaf) {
if (quadTree2.val) {
return quadTree2;
} else {
return quadTree1;
}
}
let topLeft = intersect(quadTree1.topLeft, quadTree2.topLeft);
let topRight = intersect(quadTree1.topRight, quadTree2.topRight);
let bottomLeft = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
let bottomRight = intersect(quadTree1.bottomRight, quadTree2.bottomRight);
if (topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf &&
topLeft.val === topRight.val && topLeft.val === bottomLeft.val && topLeft.val === bottomRight.val) {
return new _Node(topLeft.val, true, null, null, null, null);
}
return new _Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | n是四叉树中节点的总数，每个节点最多访问一次 |
| 空间复杂度 | O(h) | h是四叉树的高度，递归调用栈的深度，最坏情况下为O(log n) |