558.Quad Tree Intersection

558.Quad Tree Intersection
难度:Easy
四叉树是一种树数据，其中每个结点恰好有四个子结点：topLeft、topRight、bottomLeft 和 bottomRight。四叉树通常被用来划分一个二维空间，递归地将其细分为四个象限或区域。
我们希望在四叉树中存储 True/False 信息。四叉树用来表示 N * N 的布尔网格。对于每个结点, 它将被等分成四个孩子结点直到这个区域内的值都是相同的。每个节点都有另外两个布尔属性：isLeaf 和 val。当这个节点是一个叶子结点时 isLeaf 为真。val 变量储存叶子结点所代表的区域的值。
例如，下面是两个四叉树 A 和 B：
1
A:
2
+-------+-------+   T: true
3
|       |       |   F: false
4
|   T   |   T   |
5
|       |       |
6
+-------+-------+
7
|       |       |
8
|   F   |   F   |
9
|       |       |
10
+-------+-------+
11
topLeft: T
12
topRight: T
13
bottomLeft: F
14
bottomRight: F
15
​
16
B:               
17
+-------+---+---+
18
|       | F | F |
19
|   T   +---+---+
20
|       | T | T |
21
+-------+---+---+
22
|       |       |
23
|   T   |   F   |
24
|       |       |
25
+-------+-------+
26
topLeft: T
27
topRight:
28
     topLeft: F
29
     topRight: F
30
     bottomLeft: T
31
     bottomRight: T
32
bottomLeft: T
33
bottomRight: F
34
 
35
​
36
你的任务是实现一个函数，该函数根据两个四叉树返回表示这两个四叉树的逻辑或(或并)的四叉树。
37
​
38
A:                 B:                 C (A or B):
39
+-------+-------+  +-------+---+---+  +-------+-------+
40
|       |       |  |       | F | F |  |       |       |
41
|   T   |   T   |  |   T   +---+---+  |   T   |   T   |
42
|       |       |  |       | T | T |  |       |       |
43
+-------+-------+  +-------+---+---+  +-------+-------+
44
|       |       |  |       |       |  |       |       |
45
|   F   |   F   |  |   T   |   F   |  |   T   |   F   |
46
|       |       |  |       |       |  |       |       |
47
+-------+-------+  +-------+-------+  +-------+-------+
Copied!
提示：
A 和 B 都表示大小为 N * N 的网格。 N 将确保是 2 的整次幂。 如果你想了解更多关于四叉树的知识，你可以参考这个 wiki 页面。 逻辑或的定义如下：如果 A 为 True ，或者 B 为 True ，或者 A 和 B 都为 True，则 "A 或 B" 为 True。
當其中有一個爲葉子節點時，可以直接返回。
如果沒有葉子節點，則上下左右節點遞歸。
需要注意，如果最後四個都相同，需要合併爲一個葉子節點。
1
/*
2
// Definition for a QuadTree node.
3
class Node {
4
public:
5
    bool val;
6
    bool isLeaf;
7
    Node* topLeft;
8
    Node* topRight;
9
    Node* bottomLeft;
10
    Node* bottomRight;
11
​
12
    Node() {}
13
​
14
    Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
15
        val = _val;
16
        isLeaf = _isLeaf;
17
        topLeft = _topLeft;
18
        topRight = _topRight;
19
        bottomLeft = _bottomLeft;
20
        bottomRight = _bottomRight;
21
    }
22
};
23
*/
24
class Solution {
25
public:
26
    Node* intersect(Node* quadTree1, Node* quadTree2) {
27
        if(quadTree1->isLeaf) return quadTree1->val ? quadTree1 : quadTree2;
28
        if(quadTree2->isLeaf) return quadTree2->val ? quadTree2 : quadTree1;
29
        Node* topL = intersect(quadTree1->topLeft, quadTree2->topLeft);
30
        Node* topR = intersect(quadTree1->topRight, quadTree2->topRight) ;
31
        Node* bottomL = intersect(quadTree1->bottomLeft, quadTree2->bottomLeft);
32
        Node* bottomR = intersect(quadTree1->bottomRight, quadTree2->bottomRight) ;
33
        if(topL->isLeaf && topR->isLeaf && bottomL->isLeaf && bottomR->isLeaf && topL->val == topR->val && topL->val ==bottomL->val && topL->val == bottomR->val  ) return new Node(topL->val , true, NULL, NULL, NULL,NULL);
34
        
35
        return new Node(false, false, topL, topR, bottomL, bottomR);
36
​
37
    }
38
};
Copied!
执行用时 :788 ms, 在所有 C++ 提交中击败了14.84%的用户
内存消耗 :49 MB, 在所有 C++ 提交中击败了85.29%的用户

557.Reverse Words in a String

559.Maxmium Depth of N Ary Tree

Last modified 5mo ago

Copy link