101. 對(duì)稱二叉樹(shù)

給定一個(gè)二叉樹(shù)，檢查它是否是鏡像對(duì)稱的。

思路

首先想清楚，判斷對(duì)稱二叉樹(shù)要比較的是哪兩個(gè)節(jié)點(diǎn)，要比較的可不是左右節(jié)點(diǎn)！

對(duì)于二叉樹(shù)是否對(duì)稱，要比較的是根節(jié)點(diǎn)的左子樹(shù)與右子樹(shù)是不是相互翻轉(zhuǎn)的，理解這一點(diǎn)就知道了其實(shí)我們要比較的是兩個(gè)樹(shù)（這兩個(gè)樹(shù)是根節(jié)點(diǎn)的左右子樹(shù)），所以在遞歸遍歷的過(guò)程中，也是要同時(shí)遍歷兩棵樹(shù)。

那么如果比較呢？

比較的是兩個(gè)子樹(shù)的里側(cè)和外側(cè)的元素是否相等。如圖所示：

那么遍歷的順序應(yīng)該是什么樣的呢？

本題遍歷只能是“后序遍歷”，因?yàn)槲覀円ㄟ^(guò)遞歸函數(shù)的返回值來(lái)判斷兩個(gè)子樹(shù)的內(nèi)側(cè)節(jié)點(diǎn)和外側(cè)節(jié)點(diǎn)是否相等。

正是因?yàn)橐闅v兩棵樹(shù)而且要比較內(nèi)側(cè)和外側(cè)節(jié)點(diǎn)，所以準(zhǔn)確的來(lái)說(shuō)是一個(gè)樹(shù)的遍歷順序是左右中，一個(gè)樹(shù)的遍歷順序是右左中。

但都可以理解算是后序遍歷，盡管已經(jīng)不是嚴(yán)格上在一個(gè)樹(shù)上進(jìn)行遍歷的后序遍歷了。

其實(shí)后序也可以理解為是一種回溯，當(dāng)然這是題外話，講回溯的時(shí)候會(huì)重點(diǎn)講的。

說(shuō)到這大家可能感覺(jué)我有點(diǎn)啰嗦，哪有這么多道理，上來(lái)就干就完事了。別急，我說(shuō)的這些在下面的代碼講解中都有身影。

那么我們先來(lái)看看遞歸法的代碼應(yīng)該怎么寫(xiě)。

遞歸法

遞歸三部曲

確定遞歸函數(shù)的參數(shù)和返回值

因?yàn)槲覀円容^的是根節(jié)點(diǎn)的兩個(gè)子樹(shù)是否是相互翻轉(zhuǎn)的，進(jìn)而判斷這個(gè)樹(shù)是不是對(duì)稱樹(shù)，所以要比較的是兩個(gè)樹(shù)，參數(shù)自然也是左子樹(shù)節(jié)點(diǎn)和右子樹(shù)節(jié)點(diǎn)。

返回值自然是bool類(lèi)型。

代碼如下：

確定終止條件

要比較兩個(gè)節(jié)點(diǎn)數(shù)值相不相同，首先要把兩個(gè)節(jié)點(diǎn)為空的情況弄清楚！否則后面比較數(shù)值的時(shí)候就會(huì)操作空指針了。

節(jié)點(diǎn)為空的情況有：（注意我們比較的其實(shí)不是左孩子和右孩子，所以如下我稱之為左節(jié)點(diǎn)右節(jié)點(diǎn)）

左節(jié)點(diǎn)為空，右節(jié)點(diǎn)不為空，不對(duì)稱，return false

左不為空，右為空，不對(duì)稱 return false

左右都為空，對(duì)稱，返回true

此時(shí)已經(jīng)排除掉了節(jié)點(diǎn)為空的情況，那么剩下的就是左右節(jié)點(diǎn)不為空：

左右都不為空，比較節(jié)點(diǎn)數(shù)值，不相同就return false

此時(shí)左右節(jié)點(diǎn)不為空，且數(shù)值也不相同的情況我們也處理了。

代碼如下：

注意上面最后一種情況，我沒(méi)有使用else，而是elseif， 因?yàn)槲覀儼岩陨锨闆r都排除之后，剩下的就是 左右節(jié)點(diǎn)都不為空，且數(shù)值相同的情況。

確定單層遞歸的邏輯

此時(shí)才進(jìn)入單層遞歸的邏輯，單層遞歸的邏輯就是處理 右節(jié)點(diǎn)都不為空，且數(shù)值相同的情況。

比較二叉樹(shù)外側(cè)是否對(duì)稱：傳入的是左節(jié)點(diǎn)的左孩子，右節(jié)點(diǎn)的右孩子。

比較內(nèi)測(cè)是否對(duì)稱，傳入左節(jié)點(diǎn)的右孩子，右節(jié)點(diǎn)的左孩子。

如果左右都對(duì)稱就返回true ，有一側(cè)不對(duì)稱就返回false 。

代碼如下：

如上代碼中，我們可以看出使用的遍歷方式，左子樹(shù)左右中，右子樹(shù)右左中，所以我把這個(gè)遍歷順序也稱之為“后序遍歷”（盡管不是嚴(yán)格的后序遍歷）。

最后遞歸的C++整體代碼如下：

我給出的代碼并不簡(jiǎn)潔，但是把每一步判斷的邏輯都清楚的描繪出來(lái)了。

如果上來(lái)就看網(wǎng)上各種簡(jiǎn)潔的代碼，看起來(lái)真的很簡(jiǎn)單，但是很多邏輯都掩蓋掉了，而題解可能也沒(méi)有把掩蓋掉的邏輯說(shuō)清楚。

盲目的照著抄，結(jié)果就是：發(fā)現(xiàn)這是一道“簡(jiǎn)單題”，稀里糊涂的就過(guò)了，但是真正的每一步判斷邏輯未必想到清楚。

當(dāng)然我可以把如上代碼整理如下：

這個(gè)代碼就很簡(jiǎn)潔了，但隱藏了很多邏輯，條理不清晰，而且遞歸三部曲，在這里完全體現(xiàn)不出來(lái)。

所以建議大家做題的時(shí)候，一定要想清楚邏輯，每一步做什么。把道題目所有情況想到位，相應(yīng)的代碼寫(xiě)出來(lái)之后，再去追求簡(jiǎn)潔代碼的效果。

迭代法

這道題目我們也可以使用迭代法，但要注意，這里的迭代法可不是前中后序的迭代寫(xiě)法，因?yàn)楸绢}的本質(zhì)是判斷兩個(gè)樹(shù)是否是相互翻轉(zhuǎn)的，其實(shí)已經(jīng)不是所謂二叉樹(shù)遍歷的前中后序的關(guān)系了。

這里我們可以使用隊(duì)列來(lái)比較兩個(gè)樹(shù)（根節(jié)點(diǎn)的左右子樹(shù)）是否相互翻轉(zhuǎn)，（注意這不是層序遍歷）

使用隊(duì)列

通過(guò)隊(duì)列來(lái)判斷根節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的內(nèi)側(cè)和外側(cè)是否相等，如動(dòng)畫(huà)所示：

如下的條件判斷和遞歸的邏輯是一樣的。

代碼如下：

使用棧

細(xì)心的話，其實(shí)可以發(fā)現(xiàn)，這個(gè)迭代法，其實(shí)是把左右兩個(gè)子樹(shù)要比較的元素順序放進(jìn)一個(gè)容器，然后成對(duì)成對(duì)的取出來(lái)進(jìn)行比較，那么其實(shí)使用棧也是可以的。

只要把隊(duì)列原封不動(dòng)的改成棧就可以了，我下面也給出了代碼。

總結(jié)

這次我們又深度剖析了一道二叉樹(shù)的“簡(jiǎn)單題”，大家會(huì)發(fā)現(xiàn)，真正的把題目搞清楚其實(shí)并不簡(jiǎn)單，leetcode上accept了和真正掌握了還是有距離的。

我們介紹了遞歸法和迭代法，遞歸依然通過(guò)遞歸三部曲來(lái)解決了這道題目，如果只看精簡(jiǎn)的代碼根本看不出來(lái)遞歸三部曲是如果解題的。

在迭代法中我們使用了隊(duì)列，需要注意的是這不是層序遍歷，而且僅僅通過(guò)一個(gè)容器來(lái)成對(duì)的存放我們要比較的元素，知道這一本質(zhì)之后就發(fā)現(xiàn)，用隊(duì)列，用棧，甚至用數(shù)組，都是可以的。

如果已經(jīng)做過(guò)這道題目的同學(xué)，讀完文章可以再去看看這道題目，思考一下，會(huì)有不一樣的發(fā)現(xiàn)！

相關(guān)題目推薦

100.相同的樹(shù)

572.另一個(gè)樹(shù)的子樹(shù)

其他語(yǔ)言版本

Java

Python

遞歸法:

迭代法：使用隊(duì)列

迭代法：使用棧

審核編輯：劉清