101. 對稱二叉樹
給定一個(gè)二叉樹,檢查它是否是鏡像對稱的。
思路
首先想清楚,判斷對稱二叉樹要比較的是哪兩個(gè)節(jié)點(diǎn),要比較的可不是左右節(jié)點(diǎn)!
對于二叉樹是否對稱,要比較的是根節(jié)點(diǎn)的左子樹與右子樹是不是相互翻轉(zhuǎn)的,理解這一點(diǎn)就知道了其實(shí)我們要比較的是兩個(gè)樹(這兩個(gè)樹是根節(jié)點(diǎn)的左右子樹),所以在遞歸遍歷的過程中,也是要同時(shí)遍歷兩棵樹。
那么如果比較呢?
比較的是兩個(gè)子樹的里側(cè)和外側(cè)的元素是否相等。如圖所示:
那么遍歷的順序應(yīng)該是什么樣的呢?
本題遍歷只能是“后序遍歷”,因?yàn)槲覀円ㄟ^遞歸函數(shù)的返回值來判斷兩個(gè)子樹的內(nèi)側(cè)節(jié)點(diǎn)和外側(cè)節(jié)點(diǎn)是否相等。
正是因?yàn)橐闅v兩棵樹而且要比較內(nèi)側(cè)和外側(cè)節(jié)點(diǎn),所以準(zhǔn)確的來說是一個(gè)樹的遍歷順序是左右中,一個(gè)樹的遍歷順序是右左中。
但都可以理解算是后序遍歷,盡管已經(jīng)不是嚴(yán)格上在一個(gè)樹上進(jìn)行遍歷的后序遍歷了。
其實(shí)后序也可以理解為是一種回溯,當(dāng)然這是題外話,講回溯的時(shí)候會重點(diǎn)講的。
說到這大家可能感覺我有點(diǎn)啰嗦,哪有這么多道理,上來就干就完事了。別急,我說的這些在下面的代碼講解中都有身影。
那么我們先來看看遞歸法的代碼應(yīng)該怎么寫。
遞歸法
遞歸三部曲
確定遞歸函數(shù)的參數(shù)和返回值
因?yàn)槲覀円容^的是根節(jié)點(diǎn)的兩個(gè)子樹是否是相互翻轉(zhuǎn)的,進(jìn)而判斷這個(gè)樹是不是對稱樹,所以要比較的是兩個(gè)樹,參數(shù)自然也是左子樹節(jié)點(diǎn)和右子樹節(jié)點(diǎn)。
返回值自然是bool類型。
代碼如下:
確定終止條件
要比較兩個(gè)節(jié)點(diǎn)數(shù)值相不相同,首先要把兩個(gè)節(jié)點(diǎn)為空的情況弄清楚!否則后面比較數(shù)值的時(shí)候就會操作空指針了。
節(jié)點(diǎn)為空的情況有:(注意我們比較的其實(shí)不是左孩子和右孩子,所以如下我稱之為左節(jié)點(diǎn)右節(jié)點(diǎn))
左節(jié)點(diǎn)為空,右節(jié)點(diǎn)不為空,不對稱,return false
左不為空,右為空,不對稱 return false
左右都為空,對稱,返回true
此時(shí)已經(jīng)排除掉了節(jié)點(diǎn)為空的情況,那么剩下的就是左右節(jié)點(diǎn)不為空:
左右都不為空,比較節(jié)點(diǎn)數(shù)值,不相同就return false
此時(shí)左右節(jié)點(diǎn)不為空,且數(shù)值也不相同的情況我們也處理了。
代碼如下:
注意上面最后一種情況,我沒有使用else,而是elseif, 因?yàn)槲覀儼岩陨锨闆r都排除之后,剩下的就是 左右節(jié)點(diǎn)都不為空,且數(shù)值相同的情況。
確定單層遞歸的邏輯
此時(shí)才進(jìn)入單層遞歸的邏輯,單層遞歸的邏輯就是處理 右節(jié)點(diǎn)都不為空,且數(shù)值相同的情況。
比較二叉樹外側(cè)是否對稱:傳入的是左節(jié)點(diǎn)的左孩子,右節(jié)點(diǎn)的右孩子。
比較內(nèi)測是否對稱,傳入左節(jié)點(diǎn)的右孩子,右節(jié)點(diǎn)的左孩子。
如果左右都對稱就返回true ,有一側(cè)不對稱就返回false 。
代碼如下:
如上代碼中,我們可以看出使用的遍歷方式,左子樹左右中,右子樹右左中,所以我把這個(gè)遍歷順序也稱之為“后序遍歷”(盡管不是嚴(yán)格的后序遍歷)。
最后遞歸的C++整體代碼如下:
我給出的代碼并不簡潔,但是把每一步判斷的邏輯都清楚的描繪出來了。
如果上來就看網(wǎng)上各種簡潔的代碼,看起來真的很簡單,但是很多邏輯都掩蓋掉了,而題解可能也沒有把掩蓋掉的邏輯說清楚。
盲目的照著抄,結(jié)果就是:發(fā)現(xiàn)這是一道“簡單題”,稀里糊涂的就過了,但是真正的每一步判斷邏輯未必想到清楚。
當(dāng)然我可以把如上代碼整理如下:
這個(gè)代碼就很簡潔了,但隱藏了很多邏輯,條理不清晰,而且遞歸三部曲,在這里完全體現(xiàn)不出來。
所以建議大家做題的時(shí)候,一定要想清楚邏輯,每一步做什么。把道題目所有情況想到位,相應(yīng)的代碼寫出來之后,再去追求簡潔代碼的效果。
迭代法
這道題目我們也可以使用迭代法,但要注意,這里的迭代法可不是前中后序的迭代寫法,因?yàn)楸绢}的本質(zhì)是判斷兩個(gè)樹是否是相互翻轉(zhuǎn)的,其實(shí)已經(jīng)不是所謂二叉樹遍歷的前中后序的關(guān)系了。
這里我們可以使用隊(duì)列來比較兩個(gè)樹(根節(jié)點(diǎn)的左右子樹)是否相互翻轉(zhuǎn),(注意這不是層序遍歷)
使用隊(duì)列
通過隊(duì)列來判斷根節(jié)點(diǎn)的左子樹和右子樹的內(nèi)側(cè)和外側(cè)是否相等,如動畫所示:
如下的條件判斷和遞歸的邏輯是一樣的。
代碼如下:
使用棧
細(xì)心的話,其實(shí)可以發(fā)現(xiàn),這個(gè)迭代法,其實(shí)是把左右兩個(gè)子樹要比較的元素順序放進(jìn)一個(gè)容器,然后成對成對的取出來進(jìn)行比較,那么其實(shí)使用棧也是可以的。
只要把隊(duì)列原封不動的改成棧就可以了,我下面也給出了代碼。
總結(jié)
這次我們又深度剖析了一道二叉樹的“簡單題”,大家會發(fā)現(xiàn),真正的把題目搞清楚其實(shí)并不簡單,leetcode上accept了和真正掌握了還是有距離的。
我們介紹了遞歸法和迭代法,遞歸依然通過遞歸三部曲來解決了這道題目,如果只看精簡的代碼根本看不出來遞歸三部曲是如果解題的。
在迭代法中我們使用了隊(duì)列,需要注意的是這不是層序遍歷,而且僅僅通過一個(gè)容器來成對的存放我們要比較的元素,知道這一本質(zhì)之后就發(fā)現(xiàn),用隊(duì)列,用棧,甚至用數(shù)組,都是可以的。
如果已經(jīng)做過這道題目的同學(xué),讀完文章可以再去看看這道題目,思考一下,會有不一樣的發(fā)現(xiàn)!
相關(guān)題目推薦
100.相同的樹
572.另一個(gè)樹的子樹
其他語言版本
遞歸法:
迭代法:使用隊(duì)列
迭代法:使用棧
審核編輯:劉清
-
JAVA
+關(guān)注
關(guān)注
19文章
2966瀏覽量
104704 -
python
+關(guān)注
關(guān)注
56文章
4792瀏覽量
84631
原文標(biāo)題:判斷二叉樹是否對稱
文章出處:【微信號:TheAlgorithm,微信公眾號:算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
相關(guān)推薦
評論