推 SuiseiLeda: 四元樹是啥 02/27 16:16
→ Firstshadow: 大師 02/27 16:16
推 DDFox: 大師 02/27 16:16
推 pandix: 大師 02/27 16:31
推 idiont: 我好像以前在其他OJ寫過一模一樣的題目 02/27 16:41
推 pandix: 感覺先遞迴建子node再檢查是不是全部元素都一樣比較好 02/27 16:47
推 Che31128: 大師 02/27 16:59
427. Construct Quad Tree
給你一個矩陣grid請用一個四元樹來表示他，四元樹的節點結構如下所示：
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
}
val: 表示這個區塊的值，true = 1 false = 0
isLeaf: 表示這個區塊是否所有元素都一樣
Example：
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:
https://assets.leetcode.com/uploads/2020/02/12/e2mat.png
思路：
1.四元樹是一個很特別的資料結構，如果矩陣的(x1,y1)到(x2,y2)區域的所有元素
都是0或1的話這個節點就是一個葉節點，可以用一個節點來表示，如果不是的話
，我們會將這個區域平均切成四個等分，再繼續判斷他是否所有元素都一樣，
從上面的說明我們可以觀察出來建構四元樹是有遞迴關係的。
2.這邊使用dfs來建構四元樹，定義dfs(y1, x1, y2, x2)返回一個從(x1,y1)到(x2,y2)
區域所構建出來的四元樹，可以分成兩種情況：
(1)這個區域的所有元素都相同：直接返回一個葉節點，節點的值就是這個元素。
(2)這個區域存在某個元素不相同：將當前區域均分成四等分往四個區塊繼續遞迴。
3.遞迴到底之後就可以構建出四元樹了。
Java Code：
--------------------------------------------------
class Solution {
private int[][] matrix;
public Node construct(int[][] grid) {
matrix = grid;
return dfs(0, 0, matrix.length - 1, matrix.length - 1);
}
private Node dfs(int y1, int x1, int y2, int x2) {
boolean isSame = true;
int t = matrix[y1][x1];
for (int i = y1; i <= y2 && isSame; i++) {
for (int j = x1; j <= x2; j++) {
if (matrix[i][j] != t) {
isSame = false;
break;
}
}
}
// 如果全部元素都一樣直接返回
if (isSame) {
return new Node(t == 1, true);
}
Node root = new Node(t == 1, false);
// 用x軸和y軸可以計算出切分後新的左上和右下座標
int dx = x2 - x1 + 1;
int dy = y2 - y1 + 1;
root.topLeft = dfs(y1, x1, y1 + dx/2 - 1, x1 + dy/2 - 1);
root.topRight = dfs(y1, x1 + dy/2, y1 + dx/2 - 1, x2);
root.bottomLeft = dfs(y1 + dx/2, x1, y2, x1 + dy/2 - 1);
root.bottomRight = dfs(y1 + dx/2, x1 + dy/2, y2, x2);
return root;
}
}
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
public Node(boolean val, boolean isLeaf) {
this.val = val;
this.isLeaf = isLeaf;
this.topLeft = null;
this.topRight = null;
this.bottomLeft = null;
this.bottomRight = null;
}
}
--------------------------------------------------
https://i.imgur.com/acHi4CL.png
--
https://i.imgur.com/PIoxddO.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1677485649.A.560.html
※ 編輯: Rushia (122.100.75.86 臺灣), 02/27/2023 16:15:10