題目描述
這是 LeetCode 上的 558. 四叉樹交集 ,難度為 中等。
Tag : 「遞歸」
二進制矩陣中的所有元素不是 就是
給你兩個四叉樹,
quadTree1
和
quadTree2
。
其中
quadTree1
表示一個 二進制矩陣,而
quadTree2
表示另一個
請你傳回一個表示 二進制矩陣的四叉樹,它是
quadTree1
和
quadTree2
所表示的兩個二進制矩陣進行 按位邏輯或運算 的結果。
注意,當
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]
。
如果
isLeaf
或者
val
的值為
True
,則表示它在清單
[isLeaf, val]
中的值為 ;如果
isLeaf
或者
val
的值為
False
,則表示值為
示例 1:
輸入:quadTree1 = [[0,1],[1,1],[1,1],[1,0],[1,0]]
, quadTree2 = [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
輸出:[[0,0],[1,1],[1,1],[1,1],[1,0]]
解釋:quadTree1 和 quadTree2 如上所示。由四叉樹所表示的二進制矩陣也已經給出。
如果我們對這兩個矩陣進行按位邏輯或運算,則可以得到下面的二進制矩陣,由一個作為結果的四叉樹表示。
注意,我們展示的二進制矩陣僅僅是為了更好地說明題意,你無需構造二進制矩陣來獲得結果四叉樹。
示例 2:
輸入:quadTree1 = [[1,0]]
, quadTree2 = [[1,0]]
輸出:[[1,0]]
解釋:兩個數所表示的矩陣大小都為 1*1,值全為 0
結果矩陣大小為 1*1,值全為 0
示例 3:
輸入:quadTree1 = [[0,0],[1,0],[1,0],[1,1],[1,1]]
, quadTree2 = [[0,0],[1,1],[1,1],[1,0],[1,1]]
輸出:[[1,1]]
示例 4:
輸入:quadTree1 = [[0,0],[1,1],[1,0],[1,1],[1,1]]
, quadTree2 = [[0,0],[1,1],[0,1],[1,1],[1,1],null,null,null,null,[1,1],[1,0],[1,0],[1,1]]
輸出:[[0,0],[1,1],[0,1],[1,1],[1,1],null,null,null,null,[1,1],[1,0],[1,0],[1,1]]
示例 5:
輸入:quadTree1 = [[0,1],[1,0],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
, quadTree2 = [[0,1],[0,1],[1,0],[1,1],[1,0],[1,0],[1,0],[1,1],[1,1]]
輸出:[[0,0],[0,1],[0,1],[1,1],[1,0],[1,0],[1,0],[1,1],[1,1],[1,0],[1,0],[1,1],[1,1]]
提示:
-
和quadTree1
都是符合題目要求的四叉樹,每個都代表一個quadTree2
- ,其中
遞歸
為了友善,我們令
quadTree1
為
t1
,令
quadTree2
為
t2
。
根據題意,并利用給定函數作為遞歸函數,當
t1
和
t2
均為葉子節點數時,執行「與邏輯」,即若
t1
和
t2
任一值為 時,傳回該節點,否則(兩者均為 ),傳回任一節點。
然後考慮其他情況下,如何使用
t1
和
t2
構造新節點
ans
,分别使用對應位置的進行「遞歸」構造即可(即使用
t1.topLeft
和
t2.topLeft
來指派給
ans.topLeft
,其餘位置同理),要注意可能存在
t1
或
t2
其中一節點為葉子節點的情況,此時應當使用目前葉子節點和另一節點的子節點進行構造。
最後考慮什麼情況下,會産生新的葉子節點:若目前節點
ans
的四個子節點均為葉子節點,并且值相同時,
ans
會成為葉子節點,
ans
值為葉子節點的值,此時需要執行的操作為将
isLeaf
設定為
True
,修改
val
為原子節點的值,将四個原子節點置空。
Java 代碼:
class Solution {
public Node intersect(Node t1, Node t2) {
if (t1.isLeaf && t2.isLeaf) {
if (t1.val) return t1;
else if (t2.val) return t2;
else return t1;
}
Node ans = new Node();
ans.topLeft = intersect(t1.isLeaf ? t1 : t1.topLeft, t2.isLeaf ? t2 : t2.topLeft);
ans.topRight = intersect(t1.isLeaf ? t1 : t1.topRight, t2.isLeaf ? t2 : t2.topRight);
ans.bottomLeft = intersect(t1.isLeaf ? t1 : t1.bottomLeft, t2.isLeaf ? t2 : t2.bottomLeft);
ans.bottomRight = intersect(t1.isLeaf ? t1 : t1.bottomRight, t2.isLeaf ? t2 : t2.bottomRight);
boolean a = ans.topLeft.isLeaf && ans.topRight.isLeaf && ans.bottomLeft.isLeaf && ans.bottomRight.isLeaf;
boolean b = ans.topLeft.val && ans.topRight.val && ans.bottomLeft.val && ans.bottomRight.val;
boolean c = ans.topLeft.val || ans.topRight.val || ans.bottomLeft.val || ans.bottomRight.val;
ans.isLeaf = a && (b || !c);
ans.val = ans.topLeft.val;
if (ans.isLeaf) ans.topLeft = ans.topRight = ans.bottomLeft = ans.bottomRight = null;
return
TypeScript 代碼:
function intersect(t1: Node | null, t2: Node | null): Node | null {
if (t1.isLeaf && t2.isLeaf) {
if (t1.val) return t1
else if (t2.val) return t2
else return t1
}
const ans: Node = new Node()
ans.topLeft = intersect(t1.isLeaf ? t1 : t1.topLeft, t2.isLeaf ? t2 : t2.topLeft)
ans.topRight = intersect(t1.isLeaf ? t1 : t1.topRight, t2.isLeaf ? t2 : t2.topRight)
ans.bottomLeft = intersect(t1.isLeaf ? t1 : t1.bottomLeft, t2.isLeaf ? t2 : t2.bottomLeft)
ans.bottomRight = intersect(t1.isLeaf ? t1 : t1.bottomRight, t2.isLeaf ? t2 : t2.bottomRight)
const a: boolean = ans.topLeft.isLeaf && ans.topRight.isLeaf && ans.bottomLeft.isLeaf && ans.bottomRight.isLeaf
const b: boolean = ans.topLeft.val && ans.topRight.val && ans.bottomLeft.val && ans.bottomRight.val
const c: boolean = ans.topLeft.val || ans.topRight.val || ans.bottomLeft.val || ans.bottomRight.val
ans.isLeaf = a && (b || !c)
ans.val = ans.topLeft.val
if (ans.isLeaf) ans.topLeft = ans.topRight = ans.bottomLeft = ans.bottomRight = null
return
- 時間複雜度:複雜度與最終矩陣大小相關,而最終矩陣大小不會超過原矩陣大小,複雜度為
- 空間複雜度:忽略遞歸帶來的額外空間開銷,複雜度為
加餐
另外一道也是「四叉樹」相關的遞歸運用題 : 【綜合筆試題】難度 2/5,遞歸運用及字首和優化 🎉🎉
最後
這是我們「刷穿 LeetCode」系列文章的第
No.558
篇,系列開始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道題目,部分是有鎖題,我們将先把所有不帶鎖的題目刷完。
在這個系列文章裡面,除了講解解題思路以外,還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。