首页 > 代码库 > 【剑指offer】二叉树的镜像
【剑指offer】二叉树的镜像
转载请注明出处：http://blog.csdn.net/ns_code/article/details/25915971
- 这道题目与上道题目一样，採用数组来作为保存二叉树节点的数据结构，会使測试代码更easy编写。详细的实现算法在代码中比較easy看懂，不细说了，主要想说下，測试时遇到的一些问题（最后AC了）：
- 题目描写叙述：
输入一个二叉树，输出其镜像。
- 输入：
输入可能包括多个測试例子，输入以EOF结束。
对于每一个測试案例，输入的第一行为一个整数n(0<=n<=1000,n代表将要输入的二叉树节点的个数（节点从1開始编号）。接下来一行有n个数字,代表第i个二叉树节点的元素的值。接下来有n行，每行有一个字母Ci。
Ci=’d’表示第i个节点有两子孩子，紧接着是左孩子编号和右孩子编号。
Ci=’l’表示第i个节点有一个左孩子，紧接着是左孩子的编号。
Ci=’r’表示第i个节点有一个右孩子，紧接着是右孩子的编号。
Ci=’z’表示第i个节点没有子孩子。
- 输出：
相应每一个測试案例，
依照前序输出其孩子节点的元素值。
若为空输出NULL。
- 例子输入：
7 8 6 10 5 7 9 11 d 2 3 d 4 5 d 6 7 z z z z
- 例子输出：
8 10 11 9 6 7 5
- 1、先序遍历的输出要符合要求的格式，即对于每一个測试用例来说，输出的各节点元素间要有一个空格，且输出最后一个元素后要没有空格，但要输出一个换行符，这就要推断出程序什么时候遍历输出最后一个元素，再递归实现的先序遍历函数中，我没想到能使最后一个元素符合输出格式的方法，因此我这里定义了一个int数组，用来顺序保存先序遍历的节点的data，这样直接遍历输出该int数组就可以，并再循环输出中推断要输出的元素是不是最后一个输出元素，假设是，就加上换行符。
- AC代码：
#include<stdio.h> #include<stdlib.h> typedef struct BTNode { int data; int rchild; int lchild; }BTNode; /* 推断pTree1是否包括pTree2 */ void MirrorTree(BTNode *pTree,int index) { if(pTree == NULL) return; if(index == -1) return; if(pTree[index].lchild==-1 && pTree[index].rchild==-1) return; int temp = pTree[index].lchild; pTree[index].lchild = pTree[index].rchild; pTree[index].rchild = temp; if(pTree[index].lchild!=-1) MirrorTree(pTree,pTree[index].lchild); if(pTree[index].rchild!=-1) MirrorTree(pTree,pTree[index].rchild); } //这里设置全局变量i的目的是为了将先序遍历到的元素依次保存到数组preTraverse中， //其目的是为了确定最后一个输出元素，这样好调整输出的格式，使输出符合測试系统的要求。 int i = 0; void pre_traverse(BTNode *pTree,int index,int *preTraverse,int n) { if(pTree == NULL) return; if(index != -1 && i<n) { preTraverse[i++] = pTree[index].data; if(pTree[index].lchild != -1) pre_traverse(pTree,pTree[index].lchild,preTraverse,n); if(pTree[index].rchild != -1) pre_traverse(pTree,pTree[index].rchild,preTraverse,n); } } int main() { int n; while(scanf("%d",&n) != EOF) { //输入树pTree各节点的值 BTNode *pTree = NULL; if(n>0) { pTree = (BTNode *)malloc(n*sizeof(BTNode)); if(pTree == NULL) exit(EXIT_FAILURE); int i,data; //输入n个节点的data for(i=0;i<n;i++) { scanf("%d",&data); pTree[i].data = http://www.mamicode.com/data;>/**************************************************************Problem: 1521User: mmc_maodunLanguage: CResult: AcceptedTime:0 msMemory:916 kb****************************************************************/写点小插曲：今天AC了这道题后，顺道去科技楼看了下电影《年少轻狂》的拍摄，剧组进驻学校拍摄已经有一周多了，偶尔会在校园的某个地方碰到一些戏份的拍摄，这些天的晚上一直在科技楼前拍南海大学（剧中虚拟的大学）毕业舞会的镜头，虽说实验室就在科技楼，但晚上在图书馆自习，所以一直没去看过，今晚突发奇想，跑去瞄了两眼，听周围人说，前面领舞的女的就是陈妍希，我怎么看都看不出来，楼底下更是停了各种豪车：保时捷跑车、宾利老爷车。。。。尼玛演员、导演就是有钱，我等屌丝敲十几年代码都敲不出一辆宾利来，人家一部戏下来，神马都有了！
过来瞄几眼，就把我今天的跑步给耽误了，那是别人的舞台，与我无关，回去继续写程序。。。。。。
2、由于要输入字符，因此要考虑输入缓冲队列的问题，每行含有字符的数据输入后，会留下换行符，这样会在下次输入字符时被读取，造成读取字符的错误，因此在下一行数据開始输入前，要刷新缓冲区，刚開始图方面，用了fflush(stdin)，在VC++上測试通过了，可是在九度OJ上报了RE，仅仅有一组測试用例通过，多次測试了几组数据之后，怀疑应该是fflush(stdin)的错误，由于有印象在C primer plus上说过，这不是C语言标准里的东西，想gcc应该不支持，后来在网上查了下，gcc是不支持的，这是微软在自家编译器里加的，因此果断用while--getchar()来取代，替换后果然AC了，哎！还是水啊，想想离校招还有不到4个月，心里就没底！