欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-24 21:46:28
...

 

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

描述

判断一棵二叉是否关于根节点对称(镜像对称)。

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

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

输入

输入为若干个整数(不超过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;
}