算法：對(duì)稱(chēng)的二叉樹(shù)
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，用來(lái)判斷一棵二叉樹(shù)是不是對(duì)稱(chēng)的。如果一棵二叉樹(shù)和它的鏡像一樣，那么它是對(duì)稱(chēng)的。
例如，二叉樹(shù) [1,2,2,3,4,4,3] 是對(duì)稱(chēng)的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面這個(gè) [1,2,2,null,3,null,3] 則不是鏡像對(duì)稱(chēng)的:
1
/ \
2 2
\ \
3 3
示例
輸入：root = [1,2,2,3,4,4,3]
輸出：true
限制
0 <= 節(jié)點(diǎn)個(gè)數(shù) <= 1000
方法一：遞歸
算法流程：
a，b 都為空，說(shuō)明葉子結(jié)點(diǎn)遞歸完，是一顆對(duì)稱(chēng)的二叉樹(shù)
a，b 其中一個(gè)為空，說(shuō)明非對(duì)稱(chēng)
滿足對(duì)稱(chēng)的三個(gè)必備條件：
a、b 葉子節(jié)點(diǎn)值一致
a的左子節(jié)點(diǎn) 等于 b的右子節(jié)點(diǎn)
a的右子節(jié)點(diǎn) 等于 b的左子節(jié)點(diǎn)
代碼如下：
復(fù)雜度分析
時(shí)間復(fù)雜度：這里遍歷了這棵樹(shù)，漸進(jìn)時(shí)間復(fù)雜度為 O(n)。
空間復(fù)雜度：這里的空間復(fù)雜度和遞歸使用的?？臻g有關(guān)，這里遞歸層數(shù)不超過(guò) n，故漸進(jìn)空間復(fù)雜度為 O(n)。
方法二：迭代（輔助隊(duì)列）
算法流程：
初始化：我們把根節(jié)點(diǎn)入隊(duì)兩次
迭代：
每次提取兩個(gè)結(jié)點(diǎn)并比較它們的值（隊(duì)列中每?jī)蓚€(gè)連續(xù)的結(jié)點(diǎn)應(yīng)該是相等的，而且它們的子樹(shù)互為鏡像）
終結(jié)情況：
a，b 都為空，說(shuō)明葉子結(jié)點(diǎn)遞歸完，是一顆對(duì)稱(chēng)的二叉樹(shù)
a，b 其中一個(gè)為空，說(shuō)明非對(duì)稱(chēng)
a，b 節(jié)點(diǎn)的值不一致，說(shuō)明非對(duì)稱(chēng)將兩個(gè)結(jié)點(diǎn)的左右子結(jié)點(diǎn)按相反的順序插入隊(duì)列中
代碼如下：
復(fù)雜度分析
時(shí)間復(fù)雜度：O(n)，同「方法一」。
空間復(fù)雜度：這里需要用一個(gè)隊(duì)列來(lái)維護(hù)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)最多進(jìn)隊(duì)一次，出隊(duì)一次，隊(duì)列中最多不會(huì)超過(guò) n 個(gè)點(diǎn)，故漸進(jìn)空間復(fù)雜度為 O(n)。
END
本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強(qiáng)！
好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。
