Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

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

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

這道題一開(kāi)始不知道如何下手，每次遇到這種需要比較結(jié)構(gòu)的題，心里知道肯定是用遞歸比較簡(jiǎn)單，但自己沒(méi)見(jiàn)過(guò)的題還是不知道該怎么開(kāi)始，比如這里我到底要怎么去比較他們是不是對(duì)稱，那豈不是要比較完每個(gè)節(jié)點(diǎn)的值以及左右子樹(shù)？總之找不到一個(gè)很連貫的思路，或者說(shuō)對(duì)遞歸函數(shù)的結(jié)構(gòu)、寫(xiě)法太不熟練，導(dǎo)致形不成體系，沒(méi)有通用的方法可以破題。

看了答案之后一是覺(jué)得自己怎么這么笨就沒(méi)想到可以這樣做，二是覺(jué)得這類(lèi)題肯定是有通法的，比如這里的遞歸就是讓你判斷哪些情況肯定不是sysmmetric的，一一返回false, 剩下的肯定就是symmetric的了；

先是recursive的解法：

helper函數(shù)用來(lái)判斷左右子樹(shù)是否對(duì)稱。如果兩邊都為空，是對(duì)稱的（可以通過(guò)test case自己看到）。然后看幾個(gè)不對(duì)稱的情況：

• 一邊為空，一邊不為空，不對(duì)稱；
• 兩邊的val不一樣，不對(duì)稱；
• 左邊根節(jié)點(diǎn)的左子樹(shù)與右邊根節(jié)點(diǎn)的右子樹(shù)不對(duì)稱，不對(duì)稱
• 左邊根節(jié)點(diǎn)的右子樹(shù)與右邊根節(jié)點(diǎn)的左子樹(shù)不對(duì)稱，不對(duì)稱

這里構(gòu)造遞歸函數(shù)的時(shí)候最關(guān)鍵的就是后兩種情況，能把它想清楚想明白這個(gè)recursion基本就能寫(xiě)出來(lái)了。

/**
 * 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 helper(root.left, root.right);
        
    }
    
    private boolean helper(TreeNode l, TreeNode r){
        if (l == null && r == null){
            return true;
        } else if (l == null || r == null){
            return false;
        }
        if (l.val != r.val){
            return false;
        }
        if (!helper(l.left, r.right)){
            return false;
        }
        if (!helper(l.right, r.left)){
            return false;
        }
        return true;
    }
}

這道題還可以用迭代法做：用兩個(gè)queue做BFS來(lái)遍歷左右子樹(shù). 每一次poll()出來(lái)，用幾個(gè)條件來(lái)判斷是否對(duì)稱：

• 一個(gè)為空，一個(gè)不為空，肯定不對(duì)稱；
• 兩個(gè)poll()出來(lái)的元素值不同，不對(duì)稱；

注意之后每次offer進(jìn)queue,左右兩邊的順序要?jiǎng)偤孟喾矗@樣才能每次poll()出來(lái)的時(shí)候比較是否相等。 最后退出while循環(huán)后，還要判斷是不是只有一個(gè)queue是empty,如果是那說(shuō)明也是不對(duì)稱的。

/**
 * 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;
        }
        Queue<TreeNode> queueLeft = new LinkedList<>();
        Queue<TreeNode> queueRight = new LinkedList<>();
        queueLeft.offer(root);
        queueRight.offer(root);
        while (!queueLeft.isEmpty() && !queueRight.isEmpty()){
            TreeNode nodeLeft = queueLeft.poll();
            TreeNode nodeRight = queueRight.poll();
            if (nodeLeft == null && nodeRight == null){
                continue;
            } else if (nodeLeft == null || nodeRight == null){
                return false;
            }
            if (nodeLeft.val != nodeRight.val){
                return false;
            }
            queueLeft.offer(nodeLeft.left);
            queueLeft.offer(nodeLeft.right);
            queueRight.offer(nodeRight.right);
            queueRight.offer(nodeRight.left);
        }
        if (!queueLeft.isEmpty() || !queueRight.isEmpty()){
            return false;
        }
        return true;
    }
}