427.Construct Quad Tree
===
###### tags: `Medium`,`Array`,`Divide and Conquer`,`Tree`,`Matrix`
[427. Construct Quad Tree](https://leetcode.com/problems/construct-quad-tree/)
### 題目描述
Given a `n * n` matrix `grid` of `0's` and `1's` only. We want to represent the `grid` with a Quad-Tree.
Return the root of the *Quad-Tree* representing the `grid`.
Notice that you can assign the value of a node to **True** or **False** when `isLeaf` is **False**, and both are **accepted** in the answer.
A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:
* `val`: True if the node represents a grid of 1's or False if the node represents a grid of 0's.
* `isLeaf`: True if the node is leaf node on the tree or False if the node has the four children.
```
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
}
```
We can construct a Quad-Tree from a two-dimensional area using the following steps:
If the current grid has the same value (i.e all `1's` or all `0's`) set `isLeaf` True and set `val` to the value of the grid and set the four children to Null and stop.
If the current grid has different values, set `isLeaf` to False and set `val` to any value and divide the current grid into four sub-grids as shown in the photo.
Recurse for each of the children with the proper sub-grid.
If you want to know more about the Quad-Tree, you can refer to the [wiki](https://en.wikipedia.org/wiki/Quadtree).
**Quad-Tree format:**
The output represents the serialized format of a Quad-Tree using level order traversal, where null signifies a path terminator where no node exists below.
It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list `[isLeaf, val]`.
If the value of `isLeaf` or `val` is True we represent it as **1** in the list `[isLeaf, val]` and if the value of `isLeaf` or `val` is False we represent it as **0**.
### 範例
**Example 1:**
```
Input: grid = [[0,1],[1,0]]
Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Explanation: The explanation of this example is shown below:
Notice that 0 represnts False and 1 represents True in the photo representing the Quad-Tree.
```
**Example 2:**
```
Input: 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]]
Output: [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
Explanation: 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:
```
**Constraints**:
* `n` == `grid.length` == `grid[i].length`
* `n` == 2^x^ where 0 <= `x` <= 6
### 解答
#### C++
##### 思路:
1. 把2d array分成四個區塊來做Quad-tree, 某一個區塊若值都相同, 則val=該值, leaf為true, 不同則leaf為false, val可隨意填, 且還要進一步去再細分四個區塊, 直到所有leaf node的leaf值為true
2. 遞迴建構樹, 確認目前區塊值是否全一致, 一致則返回, 不一致繼續遞迴
```cpp=
class Solution {
public:
Node* helper(vector<vector<int>>& grid, int row, int col, int n)
{
bool is_same = true;
for(int i = row; i < row+n; i++)
{
for(int j = col; j < col+n; j++)
{
if(grid[i][j] != grid[row][col])
{
is_same = false;
break;
}
}
}
if(is_same)
return new Node(grid[row][col], true);
else
{
Node* cur_node = new Node(0, false);
n /= 2;
cur_node->topLeft = helper(grid, row, col, n);
cur_node->topRight = helper(grid, row, col+n, n);
cur_node->bottomLeft = helper(grid, row+n, col, n);
cur_node->bottomRight = helper(grid, row+n, col+n, n);
return cur_node;
}
}
Node* construct(vector<vector<int>>& grid) {
return helper(grid, 0, 0, grid.size());
}
};
```
Time: $O(n^2*logn)$ 每次確認n*n區塊內是否全相同, 最多做$logn$次
Extra Space: $O(n^2)$
> [name=XD] [time= Feb 27, 2023]
##### 思路
將leaf獨立出來，然後利用遞迴，只需要檢查四個孩子是否相同就好。
```cpp=
Node* zero = new Node(false, true);
Node* one = new Node(true, true);
class Solution {
public:
Node* dfs(vector<vector<int>>& grid, int i, int j, int n) {
if (n == 0) return grid[i][j] == 0 ? zero : one;
auto topLeft = dfs(grid, i, j, n >> 1);
auto topRight = dfs(grid, i, j + n, n >> 1);
auto bottomLeft = dfs(grid, i + n, j, n >> 1);
auto bottomRight = dfs(grid, i + n, j + n, n >> 1);
if (topLeft == topRight && bottomLeft == bottomRight && topLeft == bottomLeft) {
return topLeft;
}
return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
}
Node* construct(vector<vector<int>>& grid) {
return dfs(grid, 0, 0, grid.size() >> 1);
}
};
```
Time: $O(n^2)$
Space: $O(\log n)$
> [name=Yen-Chi Chen][time=Mon, Feb 27, 2023]
#### Python
```python=
class Solution:
def construct(self, grid: List[List[int]]) -> 'Node':
zero = Node(False, True, None, None, None, None)
one = Node(True, True, None, None, None, None)
def dfs(i, j, n):
if n == 0: return zero if grid[i][j] == 0 else one
tl = dfs(i, j, n >> 1)
tr = dfs(i, j + n, n >> 1)
bl = dfs(i + n, j, n >> 1)
br = dfs(i + n, j + n, n >> 1)
if tl == tr == bl == br:
return tl
return Node(False, False, tl, tr, bl, br)
return dfs(0, 0, len(grid) >> 1)
```
> [name=Yen-Chi Chen][time=Mon, Feb 27, 2023]
### Reference
[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)
Sign in with Wallet
Connect another wallet