一.题目要求
给你一个二叉树的根节点 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
进阶:你可以运用递归和迭代两种方法解决这个问题吗?
四.解题思路
递归或者迭代,递归没写出来qaq
五.代码实现
迭代
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(!root) return false;
int remained;
queue<TreeNode*> q;
vector<int> val;
q.push(root);
while(!q.empty())
{
remained = q.size();
while(remained > 0)
{
TreeNode* tmp = q.front();
q.pop();
remained--;
if(tmp->left != nullptr)
{
q.push(tmp->left);
val.push_back(tmp->left->val);
}
else
{
val.push_back(999);
}
if(tmp->right)
{
q.push(tmp->right);
val.push_back(tmp->right->val);
}
else
{
val.push_back(999);
}
}
auto t = val;
reverse(val.begin(),val.end());
if(val != t) return false;
vector<int>().swap(val);
}
return true;
}
};
递归
class Solution {
public:
bool check(TreeNode *p, TreeNode *q) {
if (!p && !q) return true;
if (!p || !q) return false;
return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
};
六.题目总结
递归的子问题没拆出来