题目
给你一个二叉树的根节点 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
解答
- 初见思路（无法通过）：
本来是想直接通过中序遍历获得一个数组，然后从数组的两端向中间进行判断，最后样例通过数为192/199，原因是如果输入为[1,2,2,2,null,2]时，中序遍历得到的数组是对称的，但是实际上这个二叉树不是对称的。因此该思路被我放弃了。
/**
* 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) {}
* };
*/
// 3241423 中序遍历 先左再中间最后右子树
class Solution {
public:
void Middle_order_traversal(TreeNode* rootNode, vector<int>& rst) {
if (rootNode) {
Middle_order_traversal(rootNode -> left, rst);
rst.push_back(rootNode -> val);
Middle_order_traversal(rootNode -> right, rst);
}
else {
rst.push_back(-1);
}
}
bool isSymmetric(TreeNode* root) {
vector<int> rst;
Middle_order_traversal(root, rst);
if (rst.size()%2==0) {
return false;
}
int left = 0, right = rst.size() - 1;
while(left < right) {
if (rst[left] != rst[right]) {
return false;
}
left++;
right--;
}
return true;
}
};- 使用递归：
在对root进行判断之后，就使用一个辅助函数对root的左子树和右子树进行判断，判断完成后分别对左子树的左子树和右子树的右子树；左子树的右子树以及右子树的左子树进行判断，两个判断结果进行与运算，递归得到最终结果。
/**
* 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 isSymmetric(TreeNode* root) {
if (root == NULL) return true; //若根节点为空，则返回true
return isSymmetricHelper(root->left, root->right);
}
bool isSymmetricHelper(TreeNode* left, TreeNode* right) {
if (left == NULL && right == NULL) return true; //若左右都为空，则返回true
// if ((left == NULL && right != NULL) || (left != NULL && right == NULL)) return false; // 左右子树一个空一个不空，返回false (下面这行更简练)
if (left == NULL || right == NULL) return false; //若左右节点有一个不为空，则返回false
if (left->val != right->val) return false; //若左右节点的值不相等，则返回false
//递归检查左右子树是否对称
return isSymmetricHelper(left->left, right->right) && isSymmetricHelper(left->right, right->left);
}
};- 使用迭代
该解决方案使用队列来存储树的节点，首先将左子树和右子树的根节点加入队列中。然后在循环中，每次取出队列的头两个节点，并比较它们是否对称，如果不对称则返回false。如果对称，则将左节点的左子树节点和右节点的右子树节点加入队列，再将左节点的右子树节点和右节点的左子树节点加入队列。如果队列为空，则说明树是对称的，返回true。
/**
* 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 isSymmetric(TreeNode* root) {
if (root == NULL) return true; //节点为空，返回true
queue<TreeNode*> q; // 定义一个队列存储节点
q.push(root->left);
q.push(root->right);
while (!q.empty()) {
TreeNode* left = q.front(); q.pop(); // 取出队列的头节点作为左节点
TreeNode* right = q.front(); q.pop(); // 取出队列的头节点作为右节点
if (left == NULL && right == NULL) continue; //如果左右节点都为空，则继续迭代
if (left == NULL || right == NULL) return false; //左右节点只有一个不为空，直接返回false
if (left->val != right->val) return false; // 左右节点值不等，直接返回false
q.push(left->left);
q.push(right->right);
q.push(left->right);
q.push(right->left); // 注意push的顺序！！！
}
return true; //若队列为空，则说明该二叉树是对称的。
}
};