101. 對稱二叉樹

給定一個二叉樹，檢查它是否是鏡像對稱的。

思路

首先想清楚，判斷對稱二叉樹要比較的是哪兩個節(jié)點，要比較的可不是左右節(jié)點！

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

那么如果比較呢？

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

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

本題遍歷只能是“后序遍歷”，因為我們要通過遞歸函數(shù)的返回值來判斷兩個子樹的內(nèi)側(cè)節(jié)點和外側(cè)節(jié)點是否相等。

正是因為要遍歷兩棵樹而且要比較內(nèi)側(cè)和外側(cè)節(jié)點，所以準(zhǔn)確的來說是一個樹的遍歷順序是左右中，一個樹的遍歷順序是右左中。

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

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

說到這大家可能感覺我有點啰嗦，哪有這么多道理，上來就干就完事了。別急，我說的這些在下面的代碼講解中都有身影。

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

遞歸法

遞歸三部曲

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

因為我們要比較的是根節(jié)點的兩個子樹是否是相互翻轉(zhuǎn)的，進(jìn)而判斷這個樹是不是對稱樹，所以要比較的是兩個樹，參數(shù)自然也是左子樹節(jié)點和右子樹節(jié)點。

返回值自然是bool類型。

代碼如下：

確定終止條件

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

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

左節(jié)點為空，右節(jié)點不為空，不對稱，return false

左不為空，右為空，不對稱 return false

左右都為空，對稱，返回true

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

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

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

代碼如下：

注意上面最后一種情況，我沒有使用else，而是elseif， 因為我們把以上情況都排除之后，剩下的就是 左右節(jié)點都不為空，且數(shù)值相同的情況。

確定單層遞歸的邏輯

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

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

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

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

代碼如下：

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

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

我給出的代碼并不簡潔，但是把每一步判斷的邏輯都清楚的描繪出來了。

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

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

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

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

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

迭代法

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

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

使用隊列

通過隊列來判斷根節(jié)點的左子樹和右子樹的內(nèi)側(cè)和外側(cè)是否相等，如動畫所示：

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

代碼如下：

使用棧

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

只要把隊列原封不動的改成棧就可以了，我下面也給出了代碼。

總結(jié)

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

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

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

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

相關(guān)題目推薦

100.相同的樹

572.另一個樹的子樹

其他語言版本

Java

Python

遞歸法:

迭代法：使用隊列

迭代法：使用棧

審核編輯：劉清