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.

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

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

先是recursive的解法：

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

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

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

/**
 * 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來遍歷左右子樹. 每一次poll()出來，用幾個(gè)條件來判斷是否對稱：

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

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

/**
 * 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;
    }
}