题目链接：101. 对称二叉树
题目：
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
提示：
- 树中节点数目在范围 [1, 1000] 内
- -100 <= Node.val <= 100
进阶：你可以运用递归和迭代两种方法解决这个问题吗？
方案一：递归
用递归法之前可以先提前了解“递归三部曲”。
本题的三部曲是：
1、确定递归的参数和返回值：对称二叉树主要是比较左右子树的节点值是否对称，可以推断出【参数：左右孩子节点，返回值：布尔类型】。
bool compare(TreeNode* leftNode, TreeNode* rightNode) {}
2、确定终止条件：如果传入的左右孩子节点都为空，则可以知道两节点对称；如果左右孩子节点任意一个为空或两节点不为空并且值不等，则两节点不对称。此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：左右都不为空，比较节点数值，不相同就return false，反之相同就return true。左右都不为空的情况则是交给递归内外侧的子树节点即可。
//左右孩子节点都为空，则两节点对称 if (!leftNode && !rightNode) return true; //左右孩子节点任意一个为空，则两节点不对称 else if (!leftNode || !rightNode) return false; //左右孩子节点不为空且值不等，则不对称 else if (leftNode->val != rightNode->val) return false;
3、确定单层逻辑：递归左右子树的外侧（左节点的左孩子和右节点的右孩子）和内侧（左节点的右孩子和右节点的左孩子），如果内外侧都对称，则return true，反之return false。
return compare(leftNode->left, rightNode->right) && compare(leftNode->right, rightNode->left);
代码（c++）：
//递归
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (!root) return true;
return compare(root->left, root->right);
}
private:
//确定递归的参数和返回值
//比较左右子树的节点值是否对称-->参数：左右孩子节点，返回值：布尔类型
bool compare(TreeNode* leftNode, TreeNode* rightNode) {
//确定终止条件
//左右孩子节点都为空，则两节点对称
if (!leftNode && !rightNode) return true;
//左右孩子节点任意一个为空，则两节点不对称
else if (!leftNode || !rightNode) return false;
//左右孩子节点不为空且值不等，则不对称
else if (leftNode->val != rightNode->val) return false;
//确定单层逻辑
//递归左右子树的外侧（左节点的左孩子和右节点的右孩子）和内侧（左节点的右孩子和右节点的左孩子）
//如果外侧和内侧都对称则为true，反之则为false
else return compare(leftNode->left, rightNode->right) && compare(leftNode->right, rightNode->left);
}
};
方案二：迭代
1、使用队列来比较两个树（根节点的左右子树）是否相互翻转
//迭代
//用队列实现
class Solution {
public:
bool isSymmetric(TreeNode* root) {
queue que;
if (root) {
//将根节点的左右孩子节点放入队列
que.push(root->left);
que.push(root->right);
}
while (!que.empty()) {
TreeNode* leftNode = que.front(); //取出左孩子节点
que.pop();
TreeNode* rightNode = que.front(); //取出右孩子节点
que.pop();
//如果左右孩子节点都为空，则对称-->结束本次循环
if (!leftNode && !rightNode) continue;
//如果左右孩子节点任意一个为空或两节点值不等，则不对称
else if (!leftNode || !rightNode || leftNode->val != rightNode->val) return false;
//往队列里放入树的外侧孩子节点
que.push(leftNode->left); //将左节点的左孩子放入队列
que.push(rightNode->right); //将右节点的右孩子放入队列
//往队列里放入树的内侧孩子节点
que.push(leftNode->right); //将左节点的右孩子放入队列
que.push(rightNode->left); //将右节点的左孩子放入队列
}
return true;
}
};
2、使用栈来比较两个树（根节点的左右子树）是否相互翻转
究其根本，本题就是比较根节点的左右子树是否相互翻转，所以无论使用队列还是用栈，目的都是一样的。因而用栈实现和用队列实现作用是相同的。
//迭代
//用栈实现
class Solution {
public:
bool isSymmetric(TreeNode* root) {
stack stk;
if (root) {
//将根节点的左右孩子节点压栈
stk.push(root->left);
stk.push(root->right);
}
while (!stk.empty()) {
TreeNode* rightNode = stk.top(); //取出右孩子节点
stk.pop();
TreeNode* leftNode = stk.top(); //取出左孩子节点
stk.pop();
//如果左右孩子节点都为空，则对称-->结束本次循环
if (!leftNode && !rightNode) continue;
//如果左右孩子节点任意一个为空或两节点值不等，则不对称
else if (!leftNode || !rightNode || leftNode->val != rightNode->val) return false;
//将树的外侧孩子节点压栈
stk.push(leftNode->left); //将左节点的左孩子压栈
stk.push(rightNode->right); //将右节点的右孩子压栈
//将树的内侧孩子节点压栈
stk.push(leftNode->right); //将左节点的右孩子压栈
stk.push(rightNode->left); //将右节点的左孩子压栈
}
return true;
}
};
