給定一個二叉樹，檢查它是否是鏡像對稱的。
例如，二叉樹?[1,2,2,3,4,4,3] 是對稱的。
? ? 1
? / \
? 2? 2
/ \ / \
3? 4 4? 3
但是下面這個?[1,2,2,null,3,null,3] 則不是鏡像對稱的:
? ? 1
? / \
? 2? 2
? \? \
? 3? ? 3
進階：
你可以運用遞歸和迭代兩種方法解決這個問題嗎？
思路一：遞歸
1、廣度優(yōu)先
關鍵點：判斷左子樹的左節(jié)點和右子樹的右節(jié)點，以及左子樹的右節(jié)點和右子樹的左節(jié)點
一是值是否相等，二是左右子樹的子節(jié)點情況是否相同
代碼如下：
lass?Solution:
????def?isSymmetric(self,?root:?TreeNode)?->?bool:
?????????if?root?is?None:?
????????????return?True
?????????def?bfs(root1,root2):
?????????????if?not?root1?and?not?root2:
?????????????????return?True
?????????????if?not?root1?or?not?root2:
?????????????????return?False
?????????????if?root1.val!=root2.val:
?????????????????return?False
?????????????return?bfs(root1.left,root2.right)?and?bfs(root1.right,root2.left)
?????????return??bfs(root.left,root.right)?
2、深度優(yōu)先
深度優(yōu)先搜索會不斷向下，關鍵點在于不斷的判斷（增加）左子樹的左節(jié)點和右節(jié)點，以及右子樹的右節(jié)點和左節(jié)點
代碼如下：
class?Solution:
????def?isSymmetric(self,?root:?TreeNode)?->?bool:
?????????left=[]
?????????right=[]
?????????leftsearch(root,left)????????
?????????rightsearch(root,right)
?????????if?left==right:
?????????????return?True
?????????else:
?????????????return?False
def?leftsearch(t,left):
????????????if?t?!=?None:
?????????????left.append(t.val)
?????????????leftsearch(t.left,left)
?????????????leftsearch(t.right,left)
????????????else:
??????????????left.append('null')
def?rightsearch(t,right):
????????????if?t?!=?None:
?????????????right.append(t.val)
?????????????rightsearch(t.right,right)
?????????????rightsearch(t.left,right)
????????????else:
??????????????right.append('null')
思路二、迭代
關鍵點：產生一個雙向隊列，隊列每一個元素是一對元素，比如左節(jié)點的左節(jié)點和右節(jié)點的右節(jié)點以及左節(jié)點的右節(jié)點和右節(jié)點的左節(jié)點
偽代碼如下：
d=collections.dueqe()
d.append((root,root))
#不斷增加隊列里的元素，直至到葉子節(jié)點，隊列不為空時一直判斷，注意隊列的每一個元素里面包含兩個節(jié)點
while d:
? ?left,right=d.popleft()?
? if not left and not right:
? ? continue
?if not left or not right:
? ?return false
if left.val!=righr.val:
return false
代碼如下：
class?Solution:
????def?isSymmetric(self,?root:?TreeNode)?->?bool:
????????deque=collections.deque()
????????deque.append([root,root])
????????while??deque:
????????????left,right?=?deque.popleft()
????????????if?not?left?and?not?right:
????????????????continue
????????????if?not?left?or?not?right:
????????????????return?False
????????????if?left.val!=right.val:
????????????????return?False
????????????deque.append([left.left,right.right])
????????????deque.append([left.right,right.left])
????????return?True
