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.

題意：判斷一個二叉樹是不是一個鏡面樹，想象把二叉樹反轉(zhuǎn)，得到的樹是不是和原樹相同。

思路：
一個二叉樹如果是鏡面樹需要滿足兩個條件：1、根節(jié)點的左右葉子節(jié)點值相同；2、左節(jié)點的左子樹是右節(jié)點的右子樹的鏡面，左節(jié)點的右子樹是右節(jié)點的左子樹的鏡面。
編碼時，首先需要對輸入的參數(shù)做校驗，即處理參數(shù)是null的幾種情況；然后比較左右節(jié)點值是否相同；如果符合條件繼續(xù)遞歸判斷各自的左右子樹是否滿足條件。

public boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return true;
    }

    return helper(root.left, root.right);
}

private boolean helper(TreeNode left, TreeNode right) {
    if (left == null && right == null) {
        return true;
    }

    if (left == null || right == null) {
        return false;
    }

    if (left.val != right.val) {
        return false;
    }

    return helper(left.left, right.right) && helper(left.right, right.left);
}

下面是非遞歸版本，思路是一樣的，需要用一個隊列來存儲每次要比較的一對鏡像節(jié)點。

public boolean isSymmetric1(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    q.add(root);
    while (!q.isEmpty()) {
        TreeNode t1 = q.poll();
        TreeNode t2 = q.poll();
        if (t1 == null && t2 == null) continue;
        if (t1 == null || t2 == null) return false;
        if (t1.val != t2.val) return false;
        q.add(t1.left);
        q.add(t2.right);
        q.add(t1.right);
        q.add(t2.left);
    }
    return true;
}