给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/symmetric-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
bool isSymmetric(TreeNode* root) {
return sym(root,root);
}
bool sym(TreeNode *t1, TreeNode *t2)
{
if((!t1&&t2)||(t1&&!t2))
return false;
else if(!t1&&!t2)
return true;
else
return(t1->val==t2->val && sym(t1->left,t2->right)
&& sym(t1->right,t2->left));
}
};
class Solution {
public:
bool isSymmetric(TreeNode* root) {
TreeNode *t1, *t2;
queue<TreeNode*> q;
q.push(root);
q.push(root);
while(!q.empty())
{
t1 = q.front();
q.pop();
t2 = q.front();
q.pop();
if((!t1&&t2)||(t1&&!t2))
return false;
else if(!t1&&!t2)
continue;
else//t1,t2都存在
{
if(t1->val != t2->val)
return false;
q.push(t1->left);
q.push(t2->right);
q.push(t1->right);
q.push(t2->left);
}
}
return true;
}
};
《剑指Offer》同题:面试题28. 对称的二叉树
递归
class Solution {
bool ans = true;
public:
bool isSymmetric(TreeNode* root) {
dfs(root,root);
return ans;
}
void dfs(TreeNode* r1, TreeNode* r2)
{
if(!ans || (!r1 && !r2))
return;
if((!r1 && r2)||(r1 && !r2))
{
ans = false;
return;
}
if(r1->val != r2->val)
ans = false;
dfs(r1->left,r2->right);
dfs(r1->right,r2->left);
}
};
循环
class Solution {
public:
bool isSymmetric(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
q.push(root);
TreeNode *r1, *r2;
while(!q.empty())
{
r1 = q.front(); q.pop();
r2 = q.front(); q.pop();
if((!r1 && r2)||(r1 && !r2))
return false;
if(r1 && r2)
{
if(r1->val != r2->val)
return false;
q.push(r1->left);
q.push(r2->right);
q.push(r1->right);
q.push(r2->left);
}
}
return true;
}
};