給定一個二叉樹，檢查它是否是鏡像對稱的。

例如，二叉樹 [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.遞歸方法

判斷對稱的條件，就是（如下圖1），左子樹L = 右子樹R，再細分就是:

I. 左子樹的左孩子等于右子樹的右孩子：L.left = R.right
II. 左子樹的右孩子等于右子樹的左孩子：L.right = R.left

根據(jù)上面的判斷條件由根節(jié)點往下遞歸：

· 當root根節(jié)點為空的時候直接返回true
· 當L和R兩個節(jié)點都為空的時候，說明已經(jīng)同時超過葉節(jié)點了，返回true
· 當L或者R只有一個節(jié)點超過葉節(jié)點了，說明樹是不對稱的返回false
· 當L 值 ≠ R 值，說明樹是不對稱的返回false

復雜度分析：

時間復雜度 O(N）： 其中 N 為二叉樹的節(jié)點數(shù)量，每次執(zhí)行遞歸可以判斷一對節(jié)點是否對稱，因此最多只需遞歸 N/2 次。
空間復雜度 O(N) ： 最差情況下，二叉樹退化為鏈表，系統(tǒng)使用 O(N)大小的?？臻g。

二叉樹退化為鏈表
          1
         / \
        2   2
       /     \
      3       3
     /         \
    4           4

1.png

/**
 * 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){
        //如果兩個節(jié)點都為空直接continue下一個循環(huán)，如果兩個節(jié)點不相等就返回false，如果其中一個節(jié)點為空就返回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），一層一層的遍歷，將用來做對比的一對對樹節(jié)點存入隊列，然后再一對一對節(jié)點拿出來比較

復雜度分析：

時間復雜度 O(N）： 其中 N 為二叉樹的節(jié)點數(shù)量，每次執(zhí)行迭代可以判斷一對節(jié)點是否對稱，因此最多只需遞歸 N/2 次。
空間復雜度 O(N) ： 采用了額外空間，隊列里面存儲了樹的節(jié)點。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        //使用層序遍歷，將每一層節(jié)點放入
        Queue<TreeNode> queue = new LinkedList<>();
        //將左子樹節(jié)點和右子樹節(jié)點按順序放進去隊列
        queue.add(root.left);
        queue.add(root.right);
        while(!queue.isEmpty()){
            TreeNode L = queue.poll();
            TreeNode R = queue.poll();
            //如果兩個節(jié)點都為空直接continue下一個循環(huán)，如果兩個節(jié)點不相等就返回false，如果其中一個節(jié)點為空就返回false
            if(L == null && R == null) continue;
            if(L == null || R == null) return false;
            if(L.val != R.val) return false;

            //將左子樹的左孩子和右子樹的右孩子放進隊列，待下一個循環(huán)拿出來對比是否相等
            queue.add(L.left);         
            queue.add(R.right);
            
            //將左子樹的右孩子和右子樹的左孩子放進隊列，待下一個循環(huán)拿出來對比是否相等
            queue.add(L.right);         
            queue.add(R.left);
        }
        return true;
    }
}