題目描述
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，用來判斷一顆二叉樹是不是對(duì)稱的。注意，如果一個(gè)二叉樹同此二叉樹的鏡像是同樣的，定義其為對(duì)稱的。
二叉樹的鏡像定義：
源二叉樹
8
/ \
6 10
/ \ / \
5 7 9 11
鏡像二叉樹
8
/ \
10 6
/ \ / \
11 9 7 5
知識(shí)點(diǎn)
二叉樹
Qiang的思路
對(duì)于這道題來說，如果自己的思路被作者的說法所引導(dǎo)了，那么就是先去求出給定二叉樹的鏡像二叉樹，然后判斷兩個(gè)樹是不是相等的。但是，這樣做顯得太笨了。
對(duì)于一個(gè)二叉樹，如果他是對(duì)稱的，那么在這個(gè)樹的對(duì)稱的節(jié)點(diǎn)的值應(yīng)該是相等的。我們按照這個(gè)思路去遍歷這個(gè)二叉樹，問題就出現(xiàn)了，二叉樹中一個(gè)節(jié)點(diǎn)的對(duì)稱節(jié)點(diǎn)如何去找呢？
我們舉個(gè)例子，根節(jié)點(diǎn)的左孩子的對(duì)稱節(jié)點(diǎn)就是根節(jié)點(diǎn)的右孩子，左孩子的左孩子的對(duì)稱點(diǎn)就是右孩子的右孩子，左孩子的右孩子節(jié)點(diǎn)的對(duì)稱點(diǎn)就是右孩子的左孩子節(jié)點(diǎn)。以此類推，一個(gè)二叉樹中一個(gè)節(jié)點(diǎn)的對(duì)稱節(jié)點(diǎn)就是按照從根到該節(jié)點(diǎn)的路徑每一步取相反方向得到的節(jié)點(diǎn)。
這個(gè)思路具體怎么實(shí)現(xiàn)呢？我們可以這樣想，如果現(xiàn)在已經(jīng)有一個(gè)節(jié)點(diǎn)a以及其對(duì)稱節(jié)點(diǎn)b了，a的左孩子的對(duì)稱節(jié)點(diǎn)就是b的右孩子節(jié)點(diǎn)，a的右孩子節(jié)點(diǎn)就是b的左孩子節(jié)點(diǎn)。OK，這就是實(shí)現(xiàn)的關(guān)鍵點(diǎn)，因?yàn)槲覀冎栏?jié)點(diǎn)的左孩子和右孩子是一對(duì)對(duì)稱節(jié)點(diǎn)，那么根據(jù)他們兩個(gè)就可以得到另外的兩對(duì)對(duì)稱節(jié)點(diǎn)，遞歸下去就能找到所有的對(duì)稱節(jié)點(diǎn)了。于是乎，代碼就出來了。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def getResult(self, left, right):
if left==None or right==None:
if left==right:
return True
return False
if left.val!=right.val:
return False
result1=self.getResult(left.left, right.right)
result2=self.getResult(left.right, right.left)
if result1==True and result2==True:
return True
return False
def isSymmetrical(self, pRoot):
# write code here
if pRoot==None:
return True
return self.getResult(pRoot.left, pRoot.right)
Book上的思路
書中說的是通過比較二叉樹的前序遍歷序列和對(duì)稱前序遍歷序列來判斷二叉樹是不是對(duì)稱的。但是通過分析其代碼可以看出，代碼的具體實(shí)現(xiàn)和我的其實(shí)是一樣的。但是解釋的角度不同。
在此，我并不認(rèn)為書上的解釋更好一些，因?yàn)闀姓f的是通過比較前序遍歷序列來判斷是不是對(duì)稱的，但是實(shí)際代碼并不是這樣做的。雖然書中的代碼可以達(dá)到前序遍歷的效果，但是卻依賴了同時(shí)向左和向右（或者是向右和向左）進(jìn)行比較，也就是說依賴了這樣寫的代碼格式。如果真的先求出先序遍歷序列和對(duì)稱先序遍歷序列，然后在判斷是不是相等，根據(jù)相同與否得到是不是對(duì)稱二叉樹，這樣的結(jié)果恐怕不是正確的，因?yàn)椴煌亩鏄淇赡軐?duì)應(yīng)的先序遍歷結(jié)果相同，然而他們之間并不是對(duì)稱的關(guān)系。舉個(gè)例子：
二叉樹
1
/
2
/
3
鏡像二叉樹
1
\
2
\
3
兩個(gè)二叉樹的先序遍歷結(jié)果都是[1,2,3]，但是并不能說第一個(gè)二叉樹就是對(duì)稱二叉樹。
作者原創(chuàng)，如需轉(zhuǎn)載及其他問題請(qǐng)郵箱聯(lián)系：lwqiang_chn@163.com。
個(gè)人網(wǎng)站：https://www.myqiang.top。
