558. Quadtree Intersection

[A quadtree] is a tree of data in which each node has exactly four children: topLeft, topRight, bottomLeft and  bottomRight. Quadtrees are often used to divide a two-dimensional space, recursively subdividing it into four quadrants or regions.

We want to store True/False information in the quadtree. N * N The boolean [grid] the quadtree is used to represent  . For each node, it will be equally divided into four child nodes until the values ​​in this area are the same . Each node has two other boolean properties: isLeaf and  isLeaf. True when this node is a leaf node  isLeaf . val The variable stores the value of the region represented by the leaf node.

For example, here are two quadtrees A and B:

A:
+-------+-------+   T: true
|       |       |   F: false
|   T   |   T   |
|       |       |
+-------+-------+
|       |       |
|   F   |   F   |
|       |       |
+-------+-------+
topLeft: T
topRight: T
bottomLeft: F
bottomRight: F

B:               
+-------+---+---+
|       | F | F |
|   T   +---+---+
|       | T | T |
+-------+---+---+
|       |       |
|   T   |   F   |
|       |       |
+-------+-------+
topLeft: T
topRight:
     topLeft: F
     topRight: F
     bottomLeft: T
     bottomRight: T
bottomLeft: T
bottomRight: F

Your task is to implement a function that returns a quadtree representing the logical OR (or union) of the two quadtrees according to them.

A:                 B:                 C (A or B):
+-------+-------+  +-------+---+---+  +-------+-------+
|       |       |  |       | F | F |  |       |       |
|   T   |   T   |  |   T   +---+---+  |   T   |   T   |
|       |       |  |       | T | T |  |       |       |
+-------+-------+  +-------+---+---+  +-------+-------+
|       |       |  |       |       |  |       |       |
|   F   |   F   |  |   T   |   F   |  |   T   |   F   |
|       |       |  |       |       |  |       |       |
+-------+-------+  +-------+-------+  +-------+-------+
hint:

  1. A and  B both represent  N * N grids of size .
  2. N Will be guaranteed to be a whole power of 2.
  3. If you want to learn more about quadtrees, you can refer to this  wiki  page.

/
// Definition for a QuadTree node.
class Node {
public:
    bool val;
    bool isLeaf;
    Node
topLeft;
    Node topRight;
    Node
bottomLeft;
    Node* bottomRight;

Node() {}

Node(bool _val, bool _isLeaf, Node _topLeft, Node _topRight, Node _bottomLeft, Node _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};
/
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 tl = intersect(quadTree1->topLeft, quadTree2->topLeft);
          Node
tr = intersect(quadTree1->topRight, quadTree2->topRight);
          Node bl = intersect(quadTree1->bottomLeft, quadTree2->bottomLeft);
          Node
br = intersect(quadTree1->bottomRight, quadTree2->bottomRight);
          if (tl->val == tr->val && tl->val == bl->val && tl->val == br->val && tl->isLeaf && tr->isLeaf && bl->isLeaf && br->isLeaf) {
              return new Node(tl->val, true, NULL, NULL, NULL, NULL);
          } else {
              return new Node(false, false, tl, tr, bl, br);
          }
    }
};

Leave a Comment

Your email address will not be published. Required fields are marked *