/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool traversal(TreeNode* left, TreeNode* right){
// left是空指针，left=0，!left为true
if (!left && !right) return true;
if (!left || !right) return false;
if (left->val != right->val) return false;
return traversal(left->left, right->right) && traversal(left->right, right->left);
}
bool isSymmetric(TreeNode* root) {
return traversal(root, root);
}
};
class Solution {
public:
bool isSymmetric(TreeNode* root) {
// 引入队列 将递归改写成迭代
std::queue<TreeNode*> que;
que.push(root), que.push(root); // 将根结点构造成对子
TreeNode *p, *q; // 二叉树的两分叉
// 分层遍历的标志
while(!que.empty()){
p = que.front(), que.pop();
q = que.front(), que.pop();
if (!p&&!q) continue;// 区别递归法不能return true; 下面还要判断其他层
if ((!p||!q)||p->val!=q->val) return false;
// 不用判断if(que->left) 下次循环中 !p||!q 能筛选 que->left为nullptr
que.push(q->left), que.push(p->right),
que.push(q->right), que.push(p->left);
//除了声明（int a, int b;）外，句中逗号可代替分号分隔，换行也可以
}
return true;
}
};