题目地址:http://xcacm.hfut.edu.cn/problem.php?id=1214

题目描述

一棵二叉树,若其与自己的镜像完全相同,就称其为镜像树(即这棵二叉树关于根完全对称)。例如
http://xcacm.hfut.edu.cn/upload/201505/tree1.png
是一棵镜像树;


http://xcacm.hfut.edu.cn/upload/201505/tree2.png
不是镜像树。
现给你一棵二叉树,请你判断其是不是镜像树。

思路

构建好二叉树在左右DFS…

AC代码

/*************************************************************************
    > File Name: 1214.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: Wed 27 May 2015 11:47:56 AM CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int tree[105]; //存放二叉树数据
int n, N; // 节点数,最大节点数
bool dfs(int l, int r) {
    if(l > N && r>N)
        return true;
    if((tree[l] != tree[r]) || (tree[l] == 0 && tree[r]!=0) || (tree[l]!=0 && tree[r]==0))
        return false;
    return dfs(2*l, 2*r+1) && dfs(2*l+1, 2*r); // 分别遍历
}



int main()
{
#ifdef Oj
     freopen("1214.in", "r", stdin);
#endif
    int T;
    cin >> T;
    while(T--) {
        cin >> n;
        N = 2*n+1;
        int a, b, c;
        memset(tree, 0, sizeof(tree));
        tree[1] = 1; // 根结点
        for(int i=0; i<n; ++i) {
            cin >> a >> b >> c;
            tree[2*a] = b;
            tree[2*a+1] = c;
        }
        int vi;
        int i=0;
        for(int nodes=1; nodes<=n; ++nodes) {
            cin >> vi;
            for(; i<=N; ++i)
                if(tree[i] == nodes)  { // 存放数据
                    tree[i] = vi;
                    ++i;
                    break;
                }
        }
        if(n==1) {
            cout << "Yes" << endl;
            continue;
        }
        if(n==2) {
            cout << "No" << endl;
            continue;
        }
        if(dfs(2,3))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;


    }
    return 0;
}