Problem statement

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

Solution

Not so difficult problem at it looks like, all we need to do is apply definitions and recursion. If one of Quad Trees is leaf, we need to return either this tree or another, depending on value of this leaf. If both Quad Trees are not leafs, let us first construct 4 children and then check if we need to merge them or not. We need to merge them if all four children are leafs and if they have the same value.

Complexity

Time complexity is O(n^2), this is number of elements in our Quad Tree.

Code

class Solution:
    def intersect(self, Q1, Q2):
        if Q1.isLeaf:
            return Q1 if Q1.val else Q2
        if Q2.isLeaf:
            return Q2 if Q2.val else Q1
        
        if not Q1.isLeaf and not Q2.isLeaf:
            N1 = self.intersect(Q1.topLeft, Q2.topLeft)
            N2 = self.intersect(Q1.topRight, Q2.topRight)
            N3 = self.intersect(Q1.bottomLeft, Q2.bottomLeft)
            N4 = self.intersect(Q1.bottomRight, Q2.bottomRight)
            
            isLeafNew = N1.isLeaf and N2.isLeaf and N3.isLeaf and N4.isLeaf
            isEqual = N1.val==N2.val==N3.val== N4.val
            
            if isLeafNew and isEqual:
                return Node(N1.val, 1, None, None, None, None)
            else:
                return Node(0, 0, N1, N2, N3, N4)