> For the complete documentation index, see [llms.txt](https://dfine.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dfine.gitbook.io/leetcode/558.quad_tree_intersection.md).

# 558.Quad Tree Intersection

**558.Quad Tree Intersection**

难度:Easy

> 四叉树是一种树数据，其中每个结点恰好有四个子结点：topLeft、topRight、bottomLeft 和 bottomRight。四叉树通常被用来划分一个二维空间，递归地将其细分为四个象限或区域。

我们希望在四叉树中存储 True/False 信息。四叉树用来表示 N \* N 的布尔网格。对于每个结点, 它将被等分成四个孩子结点直到这个区域内的值都是相同的。每个节点都有另外两个布尔属性：isLeaf 和 val。当这个节点是一个叶子结点时 isLeaf 为真。val 变量储存叶子结点所代表的区域的值。

例如，下面是两个四叉树 A 和 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
 

你的任务是实现一个函数，该函数根据两个四叉树返回表示这两个四叉树的逻辑或(或并)的四叉树。

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

提示：

A 和 B 都表示大小为 N \* N 的网格。 N 将确保是 2 的整次幂。 如果你想了解更多关于四叉树的知识，你可以参考这个 wiki 页面。 逻辑或的定义如下：如果 A 为 True ，或者 B 为 True ，或者 A 和 B 都为 True，则 "A 或 B" 为 True。

當其中有一個爲葉子節點時，可以直接返回。\
如果沒有葉子節點，則上下左右節點遞歸。\
需要注意，如果最後四個都相同，需要合併爲一個葉子節點。

```
/*
// 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* topL = intersect(quadTree1->topLeft, quadTree2->topLeft);
        Node* topR = intersect(quadTree1->topRight, quadTree2->topRight) ;
        Node* bottomL = intersect(quadTree1->bottomLeft, quadTree2->bottomLeft);
        Node* bottomR = intersect(quadTree1->bottomRight, quadTree2->bottomRight) ;
        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);
        
        return new Node(false, false, topL, topR, bottomL, bottomR);

    }
};
```

> 执行用时 :788 ms, 在所有 C++ 提交中击败了14.84%的用户\
> 内存消耗 :49 MB, 在所有 C++ 提交中击败了85.29%的用户


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://dfine.gitbook.io/leetcode/558.quad_tree_intersection.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.