# 427.Construct Quad Tree

**427.Construct Quad Tree**

难度:Easy

> 我们想要使用一棵四叉树来储存一个 N x N 的布尔值网络。网络中每一格的值只会是真或假。树的根结点代表整个网络。对于每个结点, 它将被分等成四个孩子结点直到这个区域内的值都是相同的.

每个结点还有另外两个布尔变量: isLeaf 和 val。isLeaf 当这个节点是一个叶子结点时为真。val 变量储存叶子结点所代表的区域的值。

你的任务是使用一个四叉树表示给定的网络。下面的例子将有助于你理解这个问题：

给定下面这个8 x 8 网络，我们将这样建立一个对应的四叉树：

![](https://i.loli.net/2019/05/07/5cd0f1edc3f4d.png) 由上文的定义，它能被这样分割：

![](https://i.loli.net/2019/05/07/5cd0f1ee122b1.png)

对应的四叉树应该像下面这样，每个结点由一对 (isLeaf, val) 所代表.

对于非叶子结点，val 可以是任意的，所以使用 \* 代替。

![](https://i.loli.net/2019/05/07/5cd0f1ee07a98.png)

提示：

N 将小于 1000 且确保是 2 的整次幂。 如果你想了解更多关于四叉树的知识，你可以参考这个[wiki](https://en.wikipedia.org/wiki/Quadtree)页面。

递归建立，判断和来确定是否全0或全1.

```
/*
// 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* construct(vector<vector<int>>& grid) {
        int N=grid.size();
        if(N==0) return NULL;
        int sum =0;
        for(auto r:grid)
            for(auto c: r)
                sum +=c;
       // cout<<sum<<endl;
        if( sum== N*N || sum ==0) 
        {
          return  new Node(grid[0][0],true, NULL,NULL,NULL,NULL);  
        }
        
        vector<vector<int>> tl(N/2,vector<int>(N/2,0));
        vector<vector<int>> tr(N/2,vector<int>(N/2,0));
        vector<vector<int>> bl(N/2,vector<int>(N/2,0));
        vector<vector<int>> br(N/2,vector<int>(N/2,0));
        bool ftl, ftr,fbl, fbr;
        for(int i=0;i<N/2;i++)
            for(int j=0;j<N/2;j++)
            {
                tl[i][j]=grid[i][j];
                bl[i][j]=grid[i+N/2][j];
                tr[i][j]=grid[i][j+N/2];
                br[i][j]=grid[i+N/2][j+N/2];
            }
    
       return new Node(false,false,construct(tl),construct(tr),construct(bl),construct(br));
    }
};
```


---

# Agent Instructions: 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:

```
GET https://dfine.gitbook.io/leetcode/427.construct_quad_tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
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.