題目描述
這是 LeetCode 上的 427. 建立四叉樹 ，難度為 中等。
Tag : 「遞歸」、「字首和」
給你一個 矩陣
grid
，矩陣由若幹 和 組成。請你用四叉樹表示該矩陣
grid
。
你需要傳回能表示矩陣的 四叉樹 的根結點。
注意，當
isLeaf
為
False
時，你可以把
True
或者
False
指派給節點，兩種值都會被判題機制 接受 。
四叉樹資料結構中，每個内部節點隻有四個子節點。此外，每個節點都有兩個屬性：
-
val
True
False
-
isLeaf
True
False
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public 我們可以按以下步驟為二維區域建構四叉樹：
- 如果目前網格的值相同（即，全為或者全為），将
isLeaf
True
val
Null
- 如果目前網格的值不同，将
isLeaf
False
val
- 使用适當的子網格遞歸每個子節點。
四叉樹格式：
輸出為使用層序周遊後四叉樹的序列化形式，其中
null
表示路徑終止符，其下面不存在節點。
它與二叉樹的序列化非常相似。唯一的差別是節點以清單形式表示
如果
isLeaf
或者
val
的值為
True
，則表示它在清單 中的值為 ；如果
isLeaf
或者
val
的值為
False
，則表示值為
示例 1：
輸入：grid = [[0,1],[1,0]]
輸出：[[0,1],[1,0],[1,1],[1,1],[1,0]]
解釋：請注意，在下面四叉樹的圖示中，0 表示 false，1 示例 2：
輸入：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]]
輸出：[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
解釋：網格中的所有值都不相同。我們将網格劃分為四個子網格。
topLeft，bottomLeft 和 bottomRight 均具有相同的值。
topRight 具有不同的值，是以我們将其再分為 4 示例 3：
輸入：grid = [[1,1],[1,1]]
輸出：[[1,1]] 示例 4：
輸入：grid = [[0]]
輸出：[[1,0]] 示例 5：
輸入：grid = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]
輸出：[[0,1],[1,1],[1,0],[1,0],[1,1]] 提示：
- 其中
遞歸
假定我們存在函數
Node dfs(int a, int b, int c, int d)
，其能夠傳回「以 為左上角，
那麼最終答案為
dfs(0, 0, n-1, n-1)
，不失一般性考慮「以 為左上角，
- 判斷該矩陣是否為全或全：
- 如果是則直接建立根節點（該節點四個子節點屬性均為空）并進行傳回；
- 如果不是則建立根節點，遞歸建立四個子節點并進行指派，利用左上角和右下角可算的橫縱坐标的長度為和，進而計算出将目前矩陣四等分所得到的子矩陣的左上角和右下角坐标。
由于矩陣大小最多為 ，是以判斷某個子矩陣是否為全 或全
代碼：
class Solution {
int[][] g;
public Node construct(int[][] grid) {
g = grid;
return dfs(0, 0, g.length - 1, g.length - 1);
}
Node dfs(int a, int b, int c, int {
boolean ok = true;
int t = g[a][b];
for (int i = a; i <= c && ok; i++) {
for (int j = b; j <= d && ok; j++) {
if (g[i][j] != t) ok = false;
}
}
if (ok) return new Node(t == 1, true);
Node root = new Node(t == 1, false);
int dx = c - a + 1, dy = d - b + 1;
root.topLeft = dfs(a, b, a + dx / 2 - 1, b + dy / 2 - 1);
root.topRight = dfs(a, b + dy / 2, a + dx / 2 - 1, d);
root.bottomLeft = dfs(a + dx / 2, b, c, b + dy / 2 - 1);
root.bottomRight = dfs(a + dx / 2, b + dy / 2, c, d);
return - 時間複雜度：遞歸的複雜度分析要根據主定理，假設矩陣大小為，根據主定理，單次遞歸最多會産生個子問題（由大矩陣遞歸個小矩陣），是以問題遞歸子問題數量，而子問題規模縮減系數為原本的一半（子矩陣的大小為），剩餘的為判斷全和 全的時間開銷，不考慮辨別位帶來的剪枝效果，每次判斷全或全的複雜度與目前問題規模相等，即，但整個大小為矩陣每次進行長寬減半的子矩陣拆分，最多會被拆分為次，是以這部分總的計算量為。整體複雜度為
- 空間複雜度：忽略遞歸帶來的額外空間開銷，複雜度為
遞歸（字首和優化）
使用字首和優化「判斷全 和全 」的操作：對矩陣
grid
求字首和數組
sum
，對于一個「以左上角為 ，右下角為 」的子矩陣而言，其所包含的格子總數為 個，當且僅當矩陣和為 或 時，矩陣全 或 。
代碼：
class Solution {
static int[][] sum = new int[70][70];
int[][] g;
public Node construct(int[][] grid) {
g = grid;
int n = grid.length;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + g[i - 1][j - 1];
}
}
return dfs(0, 0, n - 1, n - 1);
}
Node dfs(int a, int b, int c, int {
int cur = sum[c + 1][d + 1] - sum[a][d + 1] - sum[c + 1][b] + sum[a][b];
int dx = c - a + 1, dy = d - b + 1, tot = dx * dy;
if (cur == 0 || cur == tot) return new Node(g[a][b] == 1, true);
Node root = new Node(g[a][b] == 1, false);
root.topLeft = dfs(a, b, a + dx / 2 - 1, b + dy / 2 - 1);
root.topRight = dfs(a, b + dy / 2, a + dx / 2 - 1, d);
root.bottomLeft = dfs(a + dx / 2, b, c, b + dy / 2 - 1);
root.bottomRight = dfs(a + dx / 2, b + dy / 2, c, d);
return - 時間複雜度：分析同理，但判斷全和全的複雜度下降為，整體複雜度為
- 空間複雜度：忽略遞歸帶來的額外空間開銷，複雜度為
最後
這是我們「刷穿 LeetCode」系列文章的第
No.427
篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。
在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。