给你一个二叉树的根节点 root ， 检查它是否轴对称。

提示：

• 树中节点数目在范围 [1, 1000] 内
• -100 <= Node.val <= 100

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

理解题意：如果同时满足下面的条件，两个树互为镜像：

1. 它们的两个根结点具有相同的值
2. 每个树的右子树都与另一个树的左子树镜像对称

题解1 【栈】递归——DFS

/*** 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 dfs(TreeNode* l, TreeNode* r){if(!l && !r) return true;// 前一个条件已经排除了全空if(!l || !r) return false;// 看题说话（记住！！！）return l->val == r->val && dfs(l->left, r->right) && dfs(l->right, r->left);}bool isSymmetric(TreeNode* root) {if(! root) return true;return dfs(root->left, root->right);     }
};

题解2 【队列】迭代——BFS

class Solution {
public:bool check(TreeNode* l, TreeNode* r){queue<TreeNode*> que;que.push(l);que.push(r);while(que.size()){l = que.front();que.pop();r = que.front();que.pop();if(!l && !r) continue;if(!l || !r) return false;// l, r 非空if(l->val != r->val) return false;// 加入新的一层// 不涉及到队列内的自动排序，所以保证顺序的情况下// 加入空结点也没关系// FIFO 所以左结点的左孩子+右结点的右孩子que.push(l->left);que.push(r->right);// 左结点的右孩子+右结点的左孩子que.push(l->right);que.push(r->left); }return true;}bool isSymmetric(TreeNode* root) {if(! root) return true;return check(root, root);}
};