給定一個(gè)二叉樹，檢查它是否是鏡像對(duì)稱的。
例如责静，二叉樹 [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
你可以運(yùn)用遞歸和迭代兩種方法解決這個(gè)問(wèn)題嗎？
1.遞歸方法
判斷對(duì)稱的條件，就是（如下圖1）芜壁，左子樹L = 右子樹R韧掩，再細(xì)分就是:
I. 左子樹的左孩子等于右子樹的右孩子：L.left = R.right
II. 左子樹的右孩子等于右子樹的左孩子：L.right = R.left
根據(jù)上面的判斷條件由根節(jié)點(diǎn)往下遞歸：
· 當(dāng)root根節(jié)點(diǎn)為空的時(shí)候直接返回true
· 當(dāng)L和R兩個(gè)節(jié)點(diǎn)都為空的時(shí)候箍铲，說(shuō)明已經(jīng)同時(shí)超過(guò)葉節(jié)點(diǎn)了，返回true
· 當(dāng)L或者R只有一個(gè)節(jié)點(diǎn)超過(guò)葉節(jié)點(diǎn)了调榄，說(shuō)明樹是不對(duì)稱的返回false
· 當(dāng)L 值 ≠ R 值伦籍，說(shuō)明樹是不對(duì)稱的返回false
復(fù)雜度分析：
時(shí)間復(fù)雜度 O(N）： 其中 N 為二叉樹的節(jié)點(diǎn)數(shù)量，每次執(zhí)行遞歸可以判斷一對(duì)節(jié)點(diǎn)是否對(duì)稱侣滩，因此最多只需遞歸 N/2 次材部。
空間復(fù)雜度 O(N) ： 最差情況下旺拉，二叉樹退化為鏈表，系統(tǒng)使用 O(N)大小的椘埠兀空間艘狭。
二叉樹退化為鏈表
1
/ \
2 2
/ \
3 3
/ \
4 4
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
return recur(root.left,root.right);
}
boolean recur(TreeNode L,TreeNode R){
//如果兩個(gè)節(jié)點(diǎn)都為空直接continue下一個(gè)循環(huán)官撼，如果兩個(gè)節(jié)點(diǎn)不相等就返回false傲绣，如果其中一個(gè)節(jié)點(diǎn)為空就返回false
if(L == null && R == null) return true;
if(L == null || R == null) return false;
if(L.val != R.val) return false;
return recur(L.left,R.right) && recur(L.right, R.left);
}
}
2.迭代方法
判斷條件和上面的遞歸是一樣的菠净，用層序遍歷（ BFS）煞抬，一層一層的遍歷革答，將用來(lái)做對(duì)比的一對(duì)對(duì)樹節(jié)點(diǎn)存入隊(duì)列，然后再一對(duì)一對(duì)節(jié)點(diǎn)拿出來(lái)比較
復(fù)雜度分析：
時(shí)間復(fù)雜度 O(N）： 其中 N 為二叉樹的節(jié)點(diǎn)數(shù)量，每次執(zhí)行迭代可以判斷一對(duì)節(jié)點(diǎn)是否對(duì)稱啊易，因此最多只需遞歸 N/2 次。
空間復(fù)雜度 O(N) ： 采用了額外空間饮睬，隊(duì)列里面存儲(chǔ)了樹的節(jié)點(diǎn)租谈。
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
//使用層序遍歷，將每一層節(jié)點(diǎn)放入
Queue<TreeNode> queue = new LinkedList<>();
//將左子樹節(jié)點(diǎn)和右子樹節(jié)點(diǎn)按順序放進(jìn)去隊(duì)列
queue.add(root.left);
queue.add(root.right);
while(!queue.isEmpty()){
TreeNode L = queue.poll();
TreeNode R = queue.poll();
//如果兩個(gè)節(jié)點(diǎn)都為空直接continue下一個(gè)循環(huán)捆愁，如果兩個(gè)節(jié)點(diǎn)不相等就返回false割去，如果其中一個(gè)節(jié)點(diǎn)為空就返回false
if(L == null && R == null) continue;
if(L == null || R == null) return false;
if(L.val != R.val) return false;
//將左子樹的左孩子和右子樹的右孩子放進(jìn)隊(duì)列，待下一個(gè)循環(huán)拿出來(lái)對(duì)比是否相等
queue.add(L.left);
queue.add(R.right);
//將左子樹的右孩子和右子樹的左孩子放進(jìn)隊(duì)列牙瓢，待下一個(gè)循環(huán)拿出來(lái)對(duì)比是否相等
queue.add(L.right);
queue.add(R.left);
}
return true;
}
}
