学步园

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

For example, this binary tree is symmetric:

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

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

思路：观察题意可知，如果是对称树，则每一层的数字左右对称，因此可模拟层序遍历做这道题。本程序中，定义了两个双向队列，一个代表上一层节点，一个代表下层节点。

class Solution {
public:
    bool isSymmetricHelper(deque<TreeNode*> Q) {
        int n = Q.size();
        int L=0,R=n-1;
        if (n&1) {
            return false;
        }
        for(; L<R; L++,R--) {
            if (Q[L] == NULL) {
                if (Q[R] != NULL) {
                    return false;
                }
            }
            else {
                if (Q[R] == NULL) {
                    return false;
                }
                else {
                    if (Q[L]->val != Q[R]->val) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
    bool isSymmetric(TreeNode *root) {
        deque<TreeNode*> Q;
        deque<TreeNode*> nextQ;
        if (root == NULL || (root->left == NULL && root->right == NULL)) {
            return true;
        }
        Q.push_back(root);
        TreeNode* pNode;
        while(!Q.empty()) {
            nextQ.clear();
            while(!Q.empty()) {
                pNode = Q.front();
                if (pNode != NULL) {
                    nextQ.push_back(pNode->left);
                    nextQ.push_back(pNode->right);
                }
                Q.pop_front();
            }
            if (!isSymmetricHelper(nextQ)) {
                return false;
            }
            Q = nextQ;
        }
        return true;
    }
};