【TOJ 5435】数据结构实验：对称二叉树

 

 本文转载自：http://www.itdaan.com/blog/2018/05/05/d085905b8b25b3947fe6523cc2dd9fb3.html

描述

判断一棵二叉树是否关于根节点对称（镜像对称）。

比如下图中左边二叉树是对称的，右边则是非对称的。

输入

输入为若干个整数（不超过512）表示一棵二叉树顺序表示时的结点元素值，其中0表示二叉树对应结点为空。输入以-1结束。 

输出

如果对称输出Yes，否则输出No。

样例输入

1 2 2 3 4 4 3 -1

样例输出

 Yes

 

#include<bits/stdc++.h>
using namespace std;
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int jud(struct TreeNode*left,struct TreeNode*right)
{
    if(!left&&!right)
        return 1;
    if(!left||!right)
        return 0;
    if(left->val!=right->val)
        return 0;
    return jud(left->left,right->right)&&jud(left->right,right->left);
}
int isSymmetric(struct TreeNode* root)
{
    if(!root)
        return 1;
    return jud(root->left,root->right);
} 

TreeNode*creat()
{
    int front=1,rear=0,x;
    TreeNode*qu[1005],*t,*root=NULL;
    while(scanf("%d",&x)!=EOF,x!=-1)
    {
        if(x==0)
            t=NULL;
        else
        {
            t=new TreeNode;
            t->val=x;
            t->left=NULL;
            t->right=NULL;
        }
        qu[++rear]=t;
        if(rear==1)
            root=t;
        else
        {
            if(t&&qu[front])
            {
                if(rear%2==0)
                    qu[front]->left=t;
                else 
                    qu[front]->right=t;
            } 
            if(rear%2==1)
                front++;
        } 
    }
    return root;
}
int main()
{
    TreeNode*x=creat();
    if(isSymmetric(x))
        printf("Yes\n");
    else 
        printf("No\n");
    return 0;
}