Logical OR of Two Binary Grids Represented as Quad-Trees

Problem Id: 558 Difficulty: Medium


Intuition

Solution


class Solution:
    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':
        if quadTree1 is None or quadTree2 is None:
            return None
        return self.union(quadTree1, quadTree2)

    def union(self, node1, node2):
        if node1.isLeaf and node2.isLeaf:
            return Node(node1.val or node2.val, True, None, None, None, None)

        if not node1.isLeaf and node2.isLeaf:
            node1, node2 = node2, node1
        if node1.isLeaf and not node2.isLeaf:
            tl = self.union(node1, node2.topLeft)
            tr = self.union(node1, node2.topRight)
            bl = self.union(node1, node2.bottomLeft)
            br = self.union(node1, node2.bottomRight)
        else:
            tl = self.union(node1.topLeft, node2.topLeft)
            tr = self.union(node1.topRight, node2.topRight)
            bl = self.union(node1.bottomLeft, node2.bottomLeft)
            br = self.union(node1.bottomRight, node2.bottomRight)

        if tl.val is not None and tl.val == tr.val == bl.val == br.val:
            return Node(tl.val, True, None, None, None, None)
        return Node(None, False, tl, tr, bl, br)