FXTi's blog
0%

quad-tree-intersection

Posted on Edited on

Quad Tree Intersection – LeetCode 558

Problem

Description

A quadtree is a tree data in which each internal node has exactly four children: topLeft, topRight, bottomLeft and bottomRight. Quad trees are often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.

We want to store True/False information in our quad tree. The quad tree is used to represent a N * N boolean grid. For each node, it will be subdivided into four children nodes until the values in the region it represents are all the same. Each node has another two boolean attributes : isLeaf and val. isLeaf is true if and only if the node is a leaf node. The val attribute for a leaf node contains the value of the region it represents.

Answer

Original

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/*
// 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 && !quadTree2) 
            return nullptr;
        if (!quadTree1 || !quadTree2) 
            return quadTree1 ? quadTree1 : quadTree2;
        if (quadTree1->isLeaf) 
            return quadTree1->val ? quadTree1 : quadTree2;
        if (quadTree2->isLeaf) 
            return quadTree2->val ? quadTree2 : quadTree1;
        quadTree1->topLeft = intersect(quadTree1->topLeft, quadTree2->topLeft);
        quadTree1->topRight = intersect(quadTree1->topRight, quadTree2->topRight);
        quadTree1->bottomLeft = intersect(quadTree1->bottomLeft, quadTree2->bottomLeft);
        quadTree1->bottomRight = intersect(quadTree1->bottomRight, quadTree2->bottomRight);
        
		if((!quadTree1->topLeft && !quadTree1->topRight 
            && !quadTree1->bottomLeft && !quadTree1->bottomRight) ||
			((quadTree1->topLeft->isLeaf && quadTree1->topRight->isLeaf 
              && quadTree1->bottomLeft->isLeaf && quadTree1->bottomRight->isLeaf) && 
             ((quadTree1->topLeft->val && quadTree1->topRight->val && quadTree1->bottomLeft->val 
               && quadTree1->bottomLeft->val && quadTree1->bottomRight->val) || 
              !(quadTree1->topLeft->val || quadTree1->topRight->val 
                || quadTree1->bottomLeft->val || quadTree1->bottomRight->val)))){
            quadTree1 -> isLeaf = true;
            quadTree1 -> val = quadTree1 -> topLeft -> val;
        }
        
        return quadTree1;
    }
};

思路

需要谨慎考虑传入两指针的状态，然后是递归后获取的四指针的状态可否合一，一旦少了就错了。时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$104$ ms，排名$17.65\%$

Better

思路

还没看到更好的思路。