镜像树

题目描述

一棵二叉树，若其与自己的镜像完全相同，就称其为镜像树（即这棵二叉树关于根完全对称）。例如

是一棵镜像树；
而

不是镜像树。
现给你一棵二叉树，请你判断其是不是镜像树。

输入

第一行是一个整数数T，表示测试数据有多少组
每组数据第一行是一个正整数n(1<=n<=100)，表示二叉树中节点的数量
下面n行，每行有三个正整数a b c(1<=a<=100,0<=b,c<=100)，表示以编号a的节点为父节点，它的左孩子节点编号为b，右孩子节点编号为c，若b=0表示没有左孩子节点，c=0表示没有右孩子节点，树的根节点是编号为1的节点，节点的编号都>=1（保证数据中给出的二叉树拓扑结构是合法的）
下面一行是n个正整数vi(1<=vi<=100)，表示编号为i的节点的值。

输出

若数据中表示的二叉树是镜像树，输出“Yes”，否则输出“No”，每个输出单独占一行

样例输入

2
7
1 2 3
2 4 5
3 6 7
4 0 0
5 0 0
6 0 0
7 0 0
1 2 2 3 4 4 3
5
1 2 3
2 0 4
3 0 5
4 0 0
5 0 0
1 2 2 3 3

样例输出

Yes
No

题解

得到此二叉树的中序遍历序列，没有节点的地方以-1代替，注意判断中点是不是1。不用去建立二叉树，直接通过输入的数据进行查询就可以遍历二叉树。

代码

#include <iostream>
#include<stdio.h>
#include<vector>
using namespace std;
#define MAXN 101
int tree[MAXN][2];
int val[MAXN];
int n;

vector<int> numss;

void LDR(int rt)
{
    if(tree[rt][0]!=0)
        LDR(tree[rt][0]);
    else
        numss.push_back(-1);
    numss.push_back(val[rt-1]);
    if(tree[rt][1]!=0)
        LDR(tree[rt][1]);
    else
        numss.push_back(-1);
}


int main()
{
    int T;
    while(scanf("%d",&T)!=EOF)
    {
        while(T--)
        {
            numss.clear();
            scanf("%d",&n);
            for(int i=0; i<n; i++)
            {
                int rt,l,r;
                scanf("%d %d %d",&rt,&l,&r);
                tree[rt][0]=l;
                tree[rt][1]=r;

            }


            for(int i=0; i<n; i++)
            {
                scanf("%d",&val[i]);
            }

            LDR(1);
            bool isHW=true;
            for(int i=0;i<=numss.size()/2;i++)
            {
                if(numss[i]!=numss[numss.size()-i-1])
                    isHW=false;
            }
            if(isHW&&numss[numss.size()/2]==1)
                printf("Yes\\n");
            else
                printf("No\\n");

        }
    }
    return 0;
}