# 558. Logical OR of Two Binary Grids Represented as Quad-Trees

• Time: $O(n^2 \log_4 n)$
• Space: $O(\log_4 n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: Node* intersect(Node* quadTree1, Node* quadTree2) { if (quadTree1->isLeaf) return quadTree1->val ? quadTree1 : quadTree2; if (quadTree2->isLeaf) return quadTree2->val ? quadTree2 : quadTree1; Node* topLeft = intersect(quadTree1->topLeft, quadTree2->topLeft); Node* topRight = intersect(quadTree1->topRight, quadTree2->topRight); Node* bottomLeft = intersect(quadTree1->bottomLeft, quadTree2->bottomLeft); Node* bottomRight = intersect(quadTree1->bottomRight, quadTree2->bottomRight); if (topLeft->val == topRight->val && // topLeft->val == bottomLeft->val && // topLeft->val == bottomRight->val && // topLeft->isLeaf && topRight->isLeaf && // bottomLeft->isLeaf && bottomRight->isLeaf) return new Node(topLeft->val, true); return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public Node intersect(Node quadTree1, Node quadTree2) { if (quadTree1.isLeaf) return quadTree1.val ? quadTree1 : quadTree2; if (quadTree2.isLeaf) return quadTree2.val ? quadTree2 : quadTree1; Node topLeft = intersect(quadTree1.topLeft, quadTree2.topLeft); Node topRight = intersect(quadTree1.topRight, quadTree2.topRight); Node bottomLeft = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft); Node bottomRight = intersect(quadTree1.bottomRight, quadTree2.bottomRight); if (topLeft.val == topRight.val && // topLeft.val == bottomLeft.val && // topLeft.val == bottomRight.val && // topLeft.isLeaf && topRight.isLeaf && // bottomLeft.isLeaf && bottomRight.isLeaf) return new Node(topLeft.val, true); return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight); } }