1.题目基本信息

1.1.题目描述

二进制矩阵中的所有元素不是 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.2.题目地址

https://leetcode.cn/problems/logical-or-of-two-binary-grids-represented-as-quad-trees/description/

2.解题方法

2.1.解题思路

递归

2.2.解题步骤

第一步，递归出口。任意一个是叶子结点时，可以直接计算出结果

第二步，递归的对四个子节点进行合并

3.解题代码

python3代码

"""
# 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 intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':
        # 思路：递归
        # 第一步，递归出口。任意一个是叶子结点时，可以直接计算出结果
        if quadTree1.isLeaf:
            if quadTree1.val:
                return Node(1, True, None, None, None, None)
            else:
                return quadTree2
        elif quadTree2.isLeaf:
            return self.intersect(quadTree2, quadTree1)
        # 第二步，递归的对四个子节点进行合并
        t1 = self.intersect(quadTree1.topLeft, quadTree2.topLeft)
        t2 = self.intersect(quadTree1.topRight, quadTree2.topRight)
        t3 = self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)
        t4 = self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)
        if t1.isLeaf and t2.isLeaf and t3.isLeaf and t4.isLeaf and (t1.val == t2.val == t3.val == t4.val):
            return Node(t1.val, True)
        return Node(0, False, t1, t2, t3, t4)

4.执行结果