101. 對稱二叉樹

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

思路

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

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

那么如果比較呢？

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

那么遍歷的順序應該是什么樣的呢？

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

正是因為要遍歷兩棵樹而且要比較內側和外側節點，所以準確的來說是一個樹的遍歷順序是左右中，一個樹的遍歷順序是右左中。

但都可以理解算是后序遍歷，盡管已經不是嚴格上在一個樹上進行遍歷的后序遍歷了。

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

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

那么我們先來看看遞歸法的代碼應該怎么寫。

遞歸法

遞歸三部曲

確定遞歸函數的參數和返回值

因為我們要比較的是根節點的兩個子樹是否是相互翻轉的，進而判斷這個樹是不是對稱樹，所以要比較的是兩個樹，參數自然也是左子樹節點和右子樹節點。

返回值自然是bool類型。

代碼如下：

確定終止條件

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

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

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

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

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

此時已經排除掉了節點為空的情況，那么剩下的就是左右節點不為空：

左右都不為空，比較節點數值，不相同就return false

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

代碼如下：

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

確定單層遞歸的邏輯

此時才進入單層遞歸的邏輯，單層遞歸的邏輯就是處理 右節點都不為空，且數值相同的情況。

比較二叉樹外側是否對稱：傳入的是左節點的左孩子，右節點的右孩子。

比較內測是否對稱，傳入左節點的右孩子，右節點的左孩子。

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

代碼如下：

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

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

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

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

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

當然我可以把如上代碼整理如下：

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

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

迭代法

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

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

使用隊列

通過隊列來判斷根節點的左子樹和右子樹的內側和外側是否相等，如動畫所示：

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

代碼如下：

使用棧

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

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

總結

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

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

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

如果已經做過這道題目的同學，讀完文章可以再去看看這道題目，思考一下，會有不一樣的發現！

相關題目推薦

100.相同的樹

572.另一個樹的子樹

其他語言版本

Java

Python

遞歸法:

迭代法：使用隊列

迭代法：使用棧

審核編輯：劉清