Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
For example, this binary tree is symmetric:
1 / \ 2 2 / \ / \ 3 4 4 3But the following is not:
1 / \ 2 2 \ \ 3 3
///////////////////
#include<iostream>
#include<vector>
using namespace std;
vector<int> pq;
vector<int> pw;
struct TreeNode {
int val;
TreeNode *right;
TreeNode *left;
TreeNode(int d) : val(d),right(NULL),left(NULL) {}
};
struct TreeNode *newnode(int d)
{
struct TreeNode *node=new TreeNode(d);
return node;
};
void in1(struct TreeNode *root)
{
if ( root) {
in1(root->left);
pq.push_back(root->val);
in1(root->right);
}
}
void in2(struct TreeNode *root)
{
if ( root) {
in2(root->right);
pw.push_back(root->val);
in2(root->left);
}
}
void inorder(struct TreeNode *root)
{
int count=0;
if ( root) {
struct TreeNode *rt=root->right;
struct TreeNode *lt=root->left;
in1(lt);
in2(rt);
for(int i=0;i<pq.size();i++)
{
if(pq[i] != pw[i])
{
count=1;
break;
}
}
}
if(count == 1)
cout<<"No";
else cout<<"Yes";
}
int main()
{
struct TreeNode *root;
root=newnode(1);
root->left=newnode(2);
root->left->right=newnode(4);
root->left->left=newnode(3);
root->right=newnode(2);
root->right->right=newnode(4);
root->right->left=newnode(4);
inorder(root);
return 0;
}
No comments:
Post a Comment