給定一個(gè)二叉樹(shù)，檢查它是否是鏡像對(duì)稱的。

例如，二叉樹(shù)?[1,2,2,3,4,4,3]?是對(duì)稱的。

1/ \2 2/ \ / \ 3 4 4 3

但是下面這個(gè)?[1,2,2,null,3,null,3]?則不是鏡像對(duì)稱的:

1/ \2 2\ \3 3

說(shuō)明:

如果你可以運(yùn)用遞歸和迭代兩種方法解決這個(gè)問(wèn)題，會(huì)很加分。

?

（算法萌新，輕拍求指點(diǎn) XD 此題思路參考了官方題解。）

由于是很久沒(méi)有接觸這種類型的題目了，所以第一次拿到有點(diǎn)懵。還是看了題解才找回感覺(jué)。
看這個(gè)二叉樹(shù)是不是對(duì)稱的，主要是看二叉樹(shù)左邊和右邊的節(jié)點(diǎn)是不是各自相反。每一層都是左右顛倒。
所以通過(guò)遞歸，判斷左樹(shù)和右樹(shù)相反的節(jié)點(diǎn)的值是不是相同。
如果兩邊都為空，正常退出，說(shuō)明遞歸到樹(shù)的底部了。
如果有一邊空了另外一半沒(méi)空，說(shuō)明有一邊的節(jié)點(diǎn)沒(méi)了，另外一半還在，肯定不是對(duì)稱的樹(shù)
如果兩邊對(duì)稱，繼續(xù)遞歸節(jié)點(diǎn)的左右節(jié)點(diǎn)，直到遞歸完全或者發(fā)現(xiàn)不對(duì)稱。
代碼如下：
遞歸：

1 class Solution { 2 public boolean isSymmetric(TreeNode root) { 3 return isMirror(root, root); 4 } 5 6 boolean isMirror(TreeNode t1, TreeNode t2) 7 { 8 if (t1 == null && t2 == null) 9 return true; 10 if(t1 == null ||t2==null) 11 return false; 12 if(t1.val==t2.val) 13 { 14 return true && isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right); 15 } 16 return false; 17 } 18 19 }

?

第二種方法是迭代，雖然知道做法和用意，但是在使用上不夠熟練。大概思路就是把待處理的節(jié)點(diǎn)入隊(duì)，然后依次出隊(duì)處理，獲取新的待處理節(jié)點(diǎn)入隊(duì)。
在處理時(shí)出現(xiàn)了一個(gè)問(wèn)題，在迭代時(shí)遇到兩個(gè)都為空的節(jié)點(diǎn)不能直接退出循環(huán)，雖然可能是二叉樹(shù)的底部，但是因?yàn)檫@時(shí)隊(duì)列里可能還有其他未處理的節(jié)點(diǎn)等待處理，不能直接返回。
代碼如下：
迭代：

1 class Solution { 2 3 4 public boolean isSymmetric(TreeNode root) 5 { 6 Queue<TreeNode> queue=new LinkedList<TreeNode>(); 7 queue.add(root); 8 queue.add(root); 9 while(!queue.isEmpty()) 10 { 11 TreeNode t1=queue.poll(); 12 TreeNode t2=queue.poll(); 13 if(t1==null && t2==null) 14 continue; 15 if(t1==null || t2==null) 16 { 17 return false; 18 } 19 if(t1.val!=t2.val) 20 return false; 21 queue.add(t1.left); 22 queue.add(t2.right); 23 queue.add(t1.right); 24 queue.add(t2.left); 25 26 } 27 return true; 28 } 29 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/axiangcoding/p/9879329.html

總結(jié)

以上是生活随笔為你收集整理的领扣（LeetCode）对称二叉树 个人题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。