Tuesday, 25 August 2015

Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
    1
   / \
  2   2
 / \ / \
3  4 4  3
But 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