這是悅樂書的第260次更新，第273篇原創(chuàng)
01 看題和準(zhǔn)備
今天介紹的是LeetCode算法題中Easy級(jí)別的第127題（順位題號(hào)是558）整陌。四叉樹是樹數(shù)據(jù)，其中每個(gè)內(nèi)部節(jié)點(diǎn)恰好有四個(gè)子節(jié)點(diǎn)：topLeft，topRight她奥，bottomLeft和bottomRight瓮增。四叉樹通常用于通過遞歸地將二維空間細(xì)分為四個(gè)象限或區(qū)域來劃分二維空間。
我們想在我們的四叉樹中存儲(chǔ)true/false哩俭。四叉樹用于表示N * N布爾網(wǎng)格绷跑。對(duì)于每個(gè)節(jié)點(diǎn)，它將被細(xì)分為四個(gè)子節(jié)點(diǎn)凡资，直到它所代表的區(qū)域中的值全部相同砸捏。每個(gè)節(jié)點(diǎn)都有另外兩個(gè)布爾屬性：isLeaf和val。當(dāng)且僅當(dāng)節(jié)點(diǎn)是葉節(jié)點(diǎn)時(shí)隙赁，isLeaf才為真带膜。葉節(jié)點(diǎn)的val屬性包含它所代表的區(qū)域的值。
例如鸳谜，下面是兩個(gè)四叉樹A和B：
A:
+-------+-------+ T: true
| | | F: false
| T | T |
| | |
+-------+-------+
| | |
| F | F |
| | |
+-------+-------+
topLeft: T
topRight: T
bottomLeft: F
bottomRight: F
B:
+-------+---+---+
| | F | F |
| T +---+---+
| | T | T |
+-------+---+---+
| | |
| T | F |
| | |
+-------+-------+
topLeft: T
topRight:
topLeft: F
topRight: F
bottomLeft: T
bottomRight: T
bottomLeft: T
bottomRight: F
您的任務(wù)是實(shí)現(xiàn)一個(gè)將需要兩個(gè)四叉樹并返回表示兩棵樹的邏輯OR（或并集）的四叉樹的函數(shù)膝藕。
A: B: C (A or B):
+-------+-------+ +-------+---+---+ +-------+-------+
| | | | | F | F | | | |
| T | T | | T +---+---+ | T | T |
| | | | | T | T | | | |
+-------+-------+ +-------+---+---+ +-------+-------+
| | | | | | | | |
| F | F | | T | F | | T | F |
| | | | | | | | |
+-------+-------+ +-------+-------+ +-------+-------+
注意：
A和B都表示大小為N * N的網(wǎng)格。
N保證是2的冪咐扭。
如果您想了解有關(guān)四叉樹的更多信息芭挽，可以參考其維基。
邏輯OR運(yùn)算定義如下：如果A為true蝗肪，或者如果B為true袜爪，或者如果A和B都為true，則“A或B”為true薛闪。
本次解題使用的開發(fā)工具是eclipse辛馆，jdk使用的版本是1.8，環(huán)境是win7 64位系統(tǒng)豁延，使用Java語言編寫和測(cè)試昙篙。
02 解題
題目描述了一種新的數(shù)據(jù)結(jié)構(gòu)，四叉樹诱咏，要求計(jì)算出兩個(gè)四叉樹的并集苔可，以一個(gè)新的四叉樹作為結(jié)果返回。
一個(gè)四叉樹含多個(gè)內(nèi)部節(jié)點(diǎn)袋狞，每個(gè)內(nèi)部節(jié)點(diǎn)擁有四個(gè)子節(jié)點(diǎn)焚辅，每個(gè)節(jié)點(diǎn)擁有兩個(gè)屬性isLeaf和val，只有四個(gè)子節(jié)點(diǎn)都是葉子節(jié)點(diǎn)時(shí)苟鸯，該節(jié)點(diǎn)本身的isLeaf屬性才會(huì)為true同蜻，只有四個(gè)子節(jié)點(diǎn)的值都相同（都為true或false）時(shí)，該節(jié)點(diǎn)本身的val屬性才會(huì)為true或false早处，與其四個(gè)子節(jié)點(diǎn)的val值等同湾蔓。
我們直接使用遞歸，如果quadTree1活著quadTree2是葉子節(jié)點(diǎn)陕赃，并且其val屬性為true卵蛉，直接返回quadTree1或quadTree2颁股。如果都不是葉子節(jié)點(diǎn)，那么就對(duì)其四個(gè)子節(jié)點(diǎn)作為參數(shù)傻丝，調(diào)用自身甘有，進(jìn)行二次操作，返回的節(jié)點(diǎn)組成新的節(jié)點(diǎn)的子節(jié)點(diǎn)葡缰，接著計(jì)算新節(jié)點(diǎn)的兩個(gè)屬性isLeaf和val亏掀，最后返回該新節(jié)點(diǎn)即可。在本題中泛释，我們直接使用quadTree1作為新的節(jié)點(diǎn)滤愕，當(dāng)然，你也可以創(chuàng)建一個(gè)新的Node對(duì)象來承接怜校。
public Node intersect(Node quadTree1, Node quadTree2) {
if (quadTree1.isLeaf) {
return quadTree1.val ? quadTree1 : quadTree2;
}
if (quadTree2.isLeaf) {
return quadTree2.val ? quadTree2 : quadTree1;
}
quadTree1.topLeft = intersect(quadTree1.topLeft, quadTree2.topLeft);
quadTree1.topRight = intersect(quadTree1.topRight, quadTree2.topRight);
quadTree1.bottomLeft = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
quadTree1.bottomRight = intersect(quadTree1.bottomRight, quadTree2.bottomRight);
if (quadTree1.topLeft.isLeaf && quadTree1.topRight.isLeaf
&& quadTree1.bottomLeft.isLeaf && quadTree1.bottomRight.isLeaf
&& quadTree1.topLeft.val == quadTree1.topRight.val
&& quadTree1.topRight.val == quadTree1.bottomLeft.val
&& quadTree1.bottomLeft.val == quadTree1.bottomRight.val) {
quadTree1.isLeaf = true;
quadTree1.val = quadTree1.topLeft.val;
}
return quadTree1;
}
03 小結(jié)
算法專題目前已日更超過三個(gè)月间影，算法題文章127+篇，公眾號(hào)對(duì)話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】茄茁、【算法】魂贬、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集裙顽。
以上就是全部?jī)?nèi)容付燥，如果大家有什么好的解法思路、建議或者其他問題愈犹，可以下方留言交流键科，點(diǎn)贊、留言漩怎、轉(zhuǎn)發(fā)就是對(duì)我最大的回報(bào)和支持勋颖！
