题目链接：558. 四叉树交集
递归计算，分类讨论即可。
这道题有一个点没有说清楚，题目给定的两颗四叉树的空间划分方式都是一样的，都是从矩阵的最中间位置划分。 将大矩阵划分为四个 $\frac{1}{4}$ 大小的小矩阵。
class Node:
"""
Definition for a QuadTree 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, t1: 'Node', t2: 'Node') -> 'Node':
if t1.isLeaf and t2.isLeaf:
return Node(t1.val | t2.val, True, None, None, None, None)
elif t1.isLeaf and not t2.isLeaf:
tl, tr, bl, br = self.intersect(t1, t2.topLeft), self.intersect(t1, t2.topRight), \
self.intersect(t1, t2.bottomLeft), self.intersect(t1, t2.bottomRight)
elif not t1.isLeaf and t2.isLeaf:
tl, tr, bl, br = self.intersect(t1.topLeft, t2), self.intersect(t1.topRight, t2), \
self.intersect(t1.bottomLeft, t2), self.intersect(t1.bottomRight, t2)
else:
tl, tr, bl, br = self.intersect(t1.topLeft, t2.topLeft), \
self.intersect(t1.topRight, t2.topRight), \
self.intersect(t1.bottomLeft, t2.bottomLeft), \
self.intersect(t1.bottomRight, t2.bottomRight)
if all([tl.isLeaf, tr.isLeaf, bl.isLeaf, br.isLeaf]) and tl.val == tr.val == bl.val == br.val:
return Node(tl.val, True, None, None, None, None)
return Node(False, False, tl, tr, bl, br)