对称的二叉树

【问题】请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

【思路】首先使用递归得方法，代码非常得简洁，如果l与r都是nullptr，那么就返回真，如果只有其中一个为nullptr，那么一定不是对称二叉树，则返回false，如果都不是nullptr，则需要判断其值是否相等，并且还要递归判断（l.left, r.right）和（l.right, r.left）两组数是否相等！

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };
10 */
11 class Solution {
12 public:
13     bool isSymmetrical(TreeNode* pRoot)
14     {
15         if(pRoot == nullptr)  return true;
16         return process(pRoot->left, pRoot->right);
17     }
18 private:
19     bool process(TreeNode* l, TreeNode* r){
20         if(l == nullptr && r == nullptr)
21             return true;
22         if(l != nullptr && r != nullptr)
23             return l->val == r->val && 
24             process(l->left, r->right) &&
25             process(l->right, r->left);
26         return false;
27     }
28 };

另一种方法，可以使用类似于层次遍历的方式，使用一个队列的方式，每次将成对的元素入堆，然后成对的取出，并进行值得判断，如果相等，则进行下一次判断，不过不相等，返回false。注意，如果两者都是nullptr，则下面不执行，如果只有一个为nullptr，则返回false，因为此时成对元素已经不满足对应相等了！

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };
10 */
11 class Solution {
12 public:
13     bool isSymmetrical(TreeNode* pRoot)
14     {
15         if(pRoot == nullptr)  return true;
16         queue<TreeNode*> q;
17         q.push(pRoot->left);
18         q.push(pRoot->right);
19         while(!q.empty()){
20             // 成对的取出元素
21             TreeNode* left = q.front();
22             q.pop();
23             TreeNode* right = q.front();
24             q.pop();  // 删除头节点
25             if(left == nullptr && right == nullptr) continue;
26             if(left == nullptr || right == nullptr) return false;
27             if(left->val != right->val) return false;
28             // 成对的插入元素
29             q.push(left->left);
30             q.push(right->right);
31             q.push(left->right);
32             q.push(right->left);
33         }
34         return true;
35     }
36 };