思路和算法
题目给出两棵「 四叉树 」—— quadTree 1 ，和 quadTree 2 ，它们分别代表一个 n × n 的矩阵，且每一个子节点都是父节点对应矩阵区域的 1 / 4 区域：
- topLeft 节点为其父节点对应的矩阵区域左上角的 1 / 4 区域。
- topRight 节点为其父节点对应的矩阵区域右上角的 1 / 4 区域。
- bottomLeft 节点为其父节点对应的矩阵区域左下角的 1 / 4 区域。
- bottomRight 节点为其父节点对应的矩阵区域右下角的 1 / 4 区域。
我们需要把这两个矩阵中的对应位置的值进行「或」操作，然后返回操作后的矩阵即可。
对于 ∀x∈{0,1} ，有 0 ∣ x = x 和 1 ∣ x = 1 成立。那么我们按照两棵树的对应的节点来进行合并操作，假设当前我们操作的两个节点分别为 node 1 和 node 2 ，记节点的合并操作为 node 1 ∣ node 2 ；
1. node 1 为叶子节点时：
如果 node 1 的值为 1 ，那么 node 1 ∣ node 2 = node 1 。
否则 node 1 ∣ node 2 = node 2 。
2. node 2 为叶子节点时：
如果 node 2 的值为 1 ，那么 node 1 ∣ node 2 = node 2
否则 node 1 ∣ node 2 = node 1 。
两者都不是叶子节点时：那么分别对两者的四个子节点来进行对应的分治处理——分别进行合并操作，然后再判断合并后的四个子节点的对应区域是否都为一个全 0 或者全 1 区域，如果是则原节点为叶子节点，否则原节点不是叶子节点，且四个子节点为上面合并操作后的四个对应子节点。
代码
Python3
class Solution: def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node': if quadTree1.isLeaf: return Node(True, True) if quadTree1.val else quadTree2 if quadTree2.isLeaf: return self.intersect(quadTree2, quadTree1) o1 = self.intersect(quadTree1.topLeft, quadTree2.topLeft) o2 = self.intersect(quadTree1.topRight, quadTree2.topRight) o3 = self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft) o4 = self.intersect(quadTree1.bottomRight, quadTree2.bottomRight) if o1.isLeaf and o2.isLeaf and o3.isLeaf and o4.isLeaf and o1.val == o2.val == o3.val == o4.val: return Node(o1.val, True) return Node(False, False, o1, o2, o3, o4)
)
