分治法解四叉树交集

思路和算法题目给出两棵「 四叉树 」—— 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 区域如果是则原节点为叶子节点否则原节点不是叶子节点且四个子节点为上面合并操作后的四个对应子节点。代码Python3class 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)