<p>Given a <code>n * n</code> matrix <code>grid</code> of <code>0&#39;s</code> and <code>1&#39;s</code> only. We want to represent <code>grid</code> with a Quad-Tree.</p>

<p>Return <em>the root of the Quad-Tree representing </em><code>grid</code>.</p>

<p>A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:</p>

<ul>
	<li><code>val</code>: True if the node represents a grid of 1&#39;s or False if the node represents a grid of 0&#39;s. Notice that you can assign the <code>val</code> to True or False when <code>isLeaf</code> is False, and both are accepted in the answer.</li>
	<li><code>isLeaf</code>: True if the node is a leaf node on the tree or False if the node has four children.</li>
</ul>

<pre>
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}</pre>

<p>We can construct a Quad-Tree from a two-dimensional area using the following steps:</p>

<ol>
	<li>If the current grid has the same value (i.e all <code>1&#39;s</code> or all <code>0&#39;s</code>) set <code>isLeaf</code> True and set <code>val</code> to the value of the grid and set the four children to Null and stop.</li>
	<li>If the current grid has different values, set <code>isLeaf</code> to False and set <code>val</code> to any value and divide the current grid into four sub-grids as shown in the photo.</li>
	<li>Recurse for each of the children with the proper sub-grid.</li>
</ol>
<img alt="" src="https://assets.leetcode.com/uploads/2020/02/11/new_top.png" style="width: 777px; height: 181px;" />
<p>If you want to know more about the Quad-Tree, you can refer to the <a href="https://en.wikipedia.org/wiki/Quadtree">wiki</a>.</p>

<p><strong>Quad-Tree format:</strong></p>

<p>You don&#39;t need to read this section for solving the problem. This is only if you want to understand the output format here. The output represents the serialized format of a Quad-Tree using level order traversal, where <code>null</code> signifies a path terminator where no node exists below.</p>

<p>It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list <code>[isLeaf, val]</code>.</p>

<p>If the value of <code>isLeaf</code> or <code>val</code> is True we represent it as <strong>1</strong> in the list <code>[isLeaf, val]</code> and if the value of <code>isLeaf</code> or <code>val</code> is False we represent it as <strong>0</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/02/11/grid1.png" style="width: 777px; height: 99px;" />
<pre>
<strong>Input:</strong> grid = [[0,1],[1,0]]
<strong>Output:</strong> [[0,1],[1,0],[1,1],[1,1],[1,0]]
<strong>Explanation:</strong> The explanation of this example is shown below:
Notice that 0 represents False and 1 represents True in the photo representing the Quad-Tree.
<img alt="" src="https://assets.leetcode.com/uploads/2020/02/12/e1tree.png" style="width: 777px; height: 186px;" />
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2020/02/12/e2mat.png" style="width: 777px; height: 343px;" /></p>

<pre>
<strong>Input:</strong> grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
<strong>Output:</strong> [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
<strong>Explanation:</strong> All values in the grid are not the same. We divide the grid into four sub-grids.
The topLeft, bottomLeft and bottomRight each has the same value.
The topRight have different values so we divide it into 4 sub-grids where each has the same value.
Explanation is shown in the photo below:
<img alt="" src="https://assets.leetcode.com/uploads/2020/02/12/e2tree.png" style="width: 777px; height: 328px;" />
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == grid.length == grid[i].length</code></li>
	<li><code>n == 2<sup>x</sup></code> where <code>0 &lt;= x &lt;= 6</code></li>
</ul>

class Solution {
public:
    Node* construct(vector<vector<int>>& grid) {
        int n = grid.size();
        return constructTree(grid, {{0, 0}, {n - 1, n - 1}});
    }

    Node* constructTree(vector<vector<int>>& grid, vector<vector<int>> boundary) {
        int x1 = boundary[0][0], y1 = boundary[0][1];
        int x2 = boundary[1][0], y2 = boundary[1][1];
        // cout << x1 << " " << y1 << endl;
        // cout << x2 << " " << y2 << endl << endl; 
        Node* root = new Node(1, false);
        int n = (x2 - x1) + 1;
        int val = grid[x1][y1];
        bool isLeafNode = true; 
        for(int i = x1; i <= x2; ++i) {
            for(int j = y1; j <= y2; ++j) {
                if(val != grid[i][j]) {
                    isLeafNode = false;
                    break;
                }
            }
            if(!isLeafNode) break;
        }
        if(isLeafNode) {
            // cout << x1 << " " << y1 << endl;
            // cout << x2 << " " << y2 << endl << endl;
            root->isLeaf = true;
            root->val = val;
            return root;
        }
        // cout << "topLeft => " << x1 << " " << y1 << " " << (x1 + (n >> 1) - 1) << " " << (y1 + (n >> 1) - 1) << endl;
        // cout << "topRight => " << x1 << " " << (y1 + (n >> 1)) << " " << (x1 + (n >> 1)) << " " << (y2) << endl;
        // cout << "bottomLeft => " << (x1 + (n >> 1)) << " " << y1 << " " << x2 << " " << (y1 + (n >> 1) - 1) << endl;
        // cout << "bottomRight => " << (x1 + (n >> 1)) << " " << (y1 + (n >> 1)) << " " << x2 << " " << y2 << endl;

        // cout << endl;

        root->topLeft = constructTree(grid, {{x1, y1}, {x1 + (n >> 1) - 1, y1 + (n >> 1) - 1}});
        root->topRight = constructTree(grid, {{x1, y1 + (n >> 1)}, {x1 + (n >> 1) - 1, y2}});
        root->bottomLeft = constructTree(grid, {{x1 + (n >> 1), y1}, {x2, y1 + (n >> 1) - 1}});
        root->bottomRight = constructTree(grid, {{x1 + (n >> 1), y1 + (n >> 1)}, {x2, y2}});
        root->isLeaf = false;
        return root;
    }
};
23800