解法一：递归方法

据题意，对称二叉树定义为：「若一棵二叉树与其镜像二叉树是相同的，则其是对称的二叉树」。因此，判断一棵二叉树是否是对称的，需要从根结点开始，不断地比较左右子树的对称情况，过程如图所示。

1. 从根结点（结点）0开始，判断其左右子树是否对称，即判断「结点1所在子树」和「结点2所在子树」是否对称；
2. 为比较这两个子树的对称情况，需要分别比较各自的左右孩子的对称情况，即：比较「结点3所在子树」和「结点4所在子树」是否对称，同时也需要比较「结点5所在子树」和「结点6所在子树」是否对称；
3. 依次类推，直至遍历到叶子结点。

注意：

1. 在遍历过程中，待比较的两个结点一个为空，一个不为空，则一定不对称；
2. 在遍历过程中，待比较的两个结点取值不同，则一定不对称；

根据上述思路，代码如下：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot) {
        if (!pRoot) 
            return true;
        return helper(pRoot->left, pRoot->right);
    }
    bool helper(TreeNode* left, TreeNode* right) {
        if ((!left && right) || (left && !right)) // 两个结点不同时为空，必不对称
            return false;
        if (!left && !right) // 两个结点同时为空，对称
            return true;
        if (left->val != right->val) // 两个结点取值不同，必不对称
            return false;
        // 递归地遍历左子树的左孩子与右子树的右孩子，以及右子树的左孩子与左子树的右孩子
        return helper(left->left, right->right) && helper(left->right, right->left); 
    }

};

该方法需要遍历树的所有结点，因此时间复杂度为O(N)；该方法在递归时需要使用栈空间，最坏时间复杂度为O(N)。

解法二：非递归解法

此方法的思路需要每一层结点的对称性，实现方式利用「队列」完成非递归实现。

步骤如下：

1. 根结点入队列两次（方便后续操作）；
2. 每次将队列的「前两个」结点出队列，比较其二者是否为空、以及val值；
3. 若满足条件，将各自的左右孩子按照相反顺序入队列（如：在图示的第二步中，1、2号结点出队列，完成比较后，按照：结点1的左孩子、结点2的右孩子、结点1的右孩子、结点2的左孩子入队列）；
4. 重复上述步骤直至队列为空。

根据上述思路，实现代码如下：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot) {
        if (!pRoot)
            return true; 
        queue<TreeNode*> q; // 定义队列
        q.push(pRoot); q.push(pRoot); // 根结点入队两次
        while (!q.empty()) {
            TreeNode* n1 = q.front(); 
            q.pop(); 
            TreeNode* n2 = q.front(); 
            q.pop();
            if ((!n1 && n2) || (n1 && !n2)) // 判断是否仅有一个为空
                return false;
            if (!n1 && !n2) // 判断是否全部为空
                continue;
            if (n1->val != n2->val) // 判断值是否相等
                return false;
            // 将四个孩子入队列
            q.push(n1->left); q.push(n2->right); 
            q.push(n1->right); q.push(n2->left);
        }
        return true;
    }

};

该方法需要遍历树的所有结点，因此时间复杂度为O(N)；该方法定义队列存储结点，因此空间复杂度为O(N)。