LeetCode #427 Construct Quad Tree 建立四叉樹

427 Construct Quad Tree 建立四叉樹

Description:
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.

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:

Example 1:

grid 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:

Explanation 1

Notice that 0 represnts False and 1 represents True in the photo representing the Quad-Tree.

Example 2:

grid 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:

Explanation 2

Example 3:

Input: grid = [[1,1],[1,1]]
Output: [[1,1]]

Example 4:

Input: grid = [[0]]
Output: [[1,0]]

Example 5:

Input: grid = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]
Output: [[0,1],[1,1],[1,0],[1,0],[1,1]]

Constraints:

n == grid.length == grid[i].length
n == 2^x where 0 <= x <= 6

題目描述:
給你一個 n * n 矩陣 grid ,矩陣由若干 0 和 1 組成。請你用四叉樹表示該矩陣 grid 拴竹。

你需要返回能表示矩陣的 四叉樹 的根結(jié)點。

注意魁兼,當(dāng) isLeaf 為 False 時具篇,你可以把 True 或者 False 賦值給節(jié)點盯腌,兩種值都會被判題機(jī)制 接受 沃斤。

四叉樹數(shù)據(jù)結(jié)構(gòu)中,每個內(nèi)部節(jié)點只有四個子節(jié)點访敌。此外凉敲,每個節(jié)點都有兩個屬性:

val:儲存葉子結(jié)點所代表的區(qū)域的值。1 對應(yīng) True寺旺,0 對應(yīng) False爷抓;
isLeaf: 當(dāng)這個節(jié)點是一個葉子結(jié)點時為 True,如果它有 4 個子節(jié)點則為 False 阻塑。

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}

我們可以按以下步驟為二維區(qū)域構(gòu)建四叉樹:

如果當(dāng)前網(wǎng)格的值相同(即蓝撇,全為 0 或者全為 1),將 isLeaf 設(shè)為 True 陈莽,將 val 設(shè)為網(wǎng)格相應(yīng)的值渤昌,并將四個子節(jié)點都設(shè)為 Null 然后停止。
如果當(dāng)前網(wǎng)格的值不同走搁,將 isLeaf 設(shè)為 False独柑, 將 val 設(shè)為任意值,然后如下圖所示私植,將當(dāng)前網(wǎng)格劃分為四個子網(wǎng)格忌栅。
使用適當(dāng)?shù)淖泳W(wǎng)格遞歸每個子節(jié)點。

如果你想了解更多關(guān)于四叉樹的內(nèi)容曲稼,可以參考 wiki 索绪。

四叉樹格式:

輸出為使用層序遍歷后四叉樹的序列化形式,其中 null 表示路徑終止符贫悄,其下面不存在節(jié)點瑞驱。

它與二叉樹的序列化非常相似。唯一的區(qū)別是節(jié)點以列表形式表示 [isLeaf, val] 窄坦。

如果 isLeaf 或者 val 的值為 True 唤反,則表示它在列表 [isLeaf, val] 中的值為 1 ;如果 isLeaf 或者 val 的值為 False 鸭津,則表示值為 0 彤侍。

示例 :

示例 1:

grid 1

輸入:grid = [[0,1],[1,0]]
輸出:[[0,1],[1,0],[1,1],[1,1],[1,0]]
解釋:此示例的解釋如下:

Explanation 1

請注意,在下面四叉樹的圖示中曙博,0 表示 false拥刻,1 表示 True 怜瞒。

示例 2:

grid 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]]
解釋:網(wǎng)格中的所有值都不相同父泳。我們將網(wǎng)格劃分為四個子網(wǎng)格般哼。
topLeft,bottomLeft 和 bottomRight 均具有相同的值惠窄。
topRight 具有不同的值蒸眠,因此我們將其再分為 4 個子網(wǎng)格,這樣每個子網(wǎng)格都具有相同的值杆融。
解釋如下圖所示:

Explanation 2

示例 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]]

提示:

n == grid.length == grid[i].length
n == 2^x 其中 0 <= x <= 6

思路:

按照左上, 右上, 左下和右下分為 4個區(qū)域
檢查區(qū)域是否一致, 不一致則不是葉子節(jié)點
一致則生成葉子節(jié)點
將區(qū)域減小到 1 / 2(面積為原來的 1 / 4), 遞歸檢查
時間復(fù)雜度O(n ^ 2lgn), 空間復(fù)雜度O(1)

代碼:
C++:

/*
// Definition for a QuadTree node.
class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;
    
    Node() {
        val = false;
        isLeaf = false;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    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) 
    {
        return quad_tree(grid, 0, 0, grid.size());
    }
private:
    Node* quad_tree(vector<vector<int>>& grid, int x, int y, int offset)
    {
        for (int i = x; i < x + offset; i++) for (int j = y; j < y + offset; j++) if (grid[i][j] != grid[x][y]) return new Node(true, false, quad_tree(grid, x, y, offset >> 1), quad_tree(grid, x, y + (offset >> 1), offset >> 1), quad_tree(grid, x + (offset >> 1), y, offset >> 1), quad_tree(grid, x + (offset >> 1), y + (offset >> 1), offset >> 1));
        return new Node(grid[x][y], true);
    }
};

Java:

/*
// Definition for a QuadTree node.
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    
    public Node() {
        this.val = false;
        this.isLeaf = false;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
};
*/

class Solution {
    public Node construct(int[][] grid) {
        return quadTree(grid, 0, 0, grid.length);
    }

    private Node quadTree(int[][] grid, int x, int y, int offset) {
        for (int i = x; i < x + offset; i++) for (int j = y; j < y + offset; j++) if (grid[x][y] != grid[i][j]) return new Node(true, false, quadTree(grid, x, y, offset >> 1), quadTree(grid, x, y + (offset >> 1), offset >> 1), quadTree(grid, x + (offset >> 1), y, offset >> 1), quadTree(grid, x + (offset >> 1), y + (offset >> 1), offset >> 1));
        return new Node(grid[x][y] == 1, true);
    }
}

Python:

"""
# Definition for a QuadTree node.
class Node:
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight
"""

class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        return Node(bool(s), True) if not (s := sum(map(sum, grid))) or not (m := len(grid) >> 1) or s == 4 * m * m else Node(True, False, self.construct([g[:m] for g in grid[:m]]), self.construct([g[m:] for g in grid[:m]]), self.construct([g[:m] for g in grid[m:]]), self.construct([g[m:] for g in grid[m:]]))
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末楞卡,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子脾歇,更是在濱河造成了極大的恐慌蒋腮,老刑警劉巖,帶你破解...
    沈念sama閱讀 218,284評論 6 506
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件藕各,死亡現(xiàn)場離奇詭異池摧,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)激况,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,115評論 3 395
  • 文/潘曉璐 我一進(jìn)店門作彤,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人乌逐,你說我怎么就攤上這事竭讳。” “怎么了浙踢?”我有些...
    開封第一講書人閱讀 164,614評論 0 354
  • 文/不壞的土叔 我叫張陵绢慢,是天一觀的道長。 經(jīng)常有香客問我成黄,道長呐芥,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,671評論 1 293
  • 正文 為了忘掉前任奋岁,我火速辦了婚禮思瘟,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘闻伶。我一直安慰自己滨攻,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 67,699評論 6 392
  • 文/花漫 我一把揭開白布蓝翰。 她就那樣靜靜地躺著光绕,像睡著了一般。 火紅的嫁衣襯著肌膚如雪畜份。 梳的紋絲不亂的頭發(fā)上诞帐,一...
    開封第一講書人閱讀 51,562評論 1 305
  • 那天,我揣著相機(jī)與錄音爆雹,去河邊找鬼停蕉。 笑死愕鼓,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的慧起。 我是一名探鬼主播菇晃,決...
    沈念sama閱讀 40,309評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼蚓挤!你這毒婦竟也來了磺送?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 39,223評論 0 276
  • 序言:老撾萬榮一對情侶失蹤灿意,失蹤者是張志新(化名)和其女友劉穎估灿,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體缤剧,經(jīng)...
    沈念sama閱讀 45,668評論 1 314
  • 正文 獨居荒郊野嶺守林人離奇死亡甲捏,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,859評論 3 336
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了鞭执。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片司顿。...
    茶點故事閱讀 39,981評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖兄纺,靈堂內(nèi)的尸體忽然破棺而出大溜,到底是詐尸還是另有隱情,我是刑警寧澤估脆,帶...
    沈念sama閱讀 35,705評論 5 347
  • 正文 年R本政府宣布钦奋,位于F島的核電站,受9級特大地震影響疙赠,放射性物質(zhì)發(fā)生泄漏付材。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 41,310評論 3 330
  • 文/蒙蒙 一圃阳、第九天 我趴在偏房一處隱蔽的房頂上張望衷戈。 院中可真熱鬧孤里,春花似錦、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,904評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽讨盒。三九已至豌习,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間银萍,已是汗流浹背变勇。 一陣腳步聲響...
    開封第一講書人閱讀 33,023評論 1 270
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留贴唇,地道東北人搀绣。 一個月前我還...
    沈念sama閱讀 48,146評論 3 370
  • 正文 我出身青樓赃梧,卻偏偏與公主長得像,于是被迫代替她去往敵國和親豌熄。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 44,933評論 2 355

推薦閱讀更多精彩內(nèi)容