剑指Offer - 九度1523 - 从上往下打印二叉树

剑指Offer - 九度1523 - 从上往下打印二叉树
2013-12-01 00:35

题目描述：: 从上往下打印出二叉树的每个节点，同层节点从左至右打印。

输入：: 输入可能包含多个测试样例，输入以EOF结束。
对于每个测试案例，输入的第一行一个整数n(1<=n<=1000, ：n代表将要输入的二叉树元素的个数（节点从1开始编号）。接下来一行有n个数字,代表第i个二叉树节点的元素的值。接下来有n行，每行有一个字母Ci。
Ci=’d’表示第i个节点有两子孩子，紧接着是左孩子编号和右孩子编号。
Ci=’l’表示第i个节点有一个左孩子，紧接着是左孩子的编号。
Ci=’r’表示第i个节点有一个右孩子，紧接着是右孩子的编号。
Ci=’z’表示第i个节点没有子孩子。

输出：: 对应每个测试案例，
按照从上之下，从左至右打印出二叉树节点的值。

样例输入：

7

8 6 5 7 10 9 11

d 2 5

d 3 4

z

z

d 6 7

z

z

样例输出：

8 6 10 5 7 9 11

题意分析：
　　很典型的level-order traversal问题。当我们需要从上至下，从左至右遍历二叉树时，用队列是最好的办法了。思路如下：
　　　　1. 初始化时，将根节点push入队
　　　　2. 只要队列不为空，就pop出一个元素进行输出，并将这个元素的左右孩子(如果不为空)依次push进队。
　　　　3. 队列为空时，算法执行结束。
　　那么，怎么确定这个算法是对的呢？
　　　　首先是从上至下，对于每个节点，都将它的左右孩子入队，两者深度相差1。因此遍历出来的结果中，第n+1层的结果必然紧跟第n层之后。
　　　　然后是从左至右，对于每个节点，都是从左至右将子节点入队，所以对于同一层的结果顺序肯定是满足从左至右的。
　　说实话，写个能ac的代码不算什么大本事，能严格证明自己程序的正确性才是真牛人...或许我读完了《算法导论》后能给这篇文章补上个严格的推理过程。不得不感叹自己还是荒废太多时间了，大学四年都没读几本像样的书，已然二十三岁高龄，老大徒伤悲矣~一万小时却还连一半都没攒到，难怪水平这么菜了。
　　输入数据要注意：根节点是哪一个，题目并没指定，所以要根据入度来判断哪个才是根，根节点入度为0。

 // 652502    zhuli19901106    1523    Accepted    点击此处查看所有case的执行结果    1052KB    1528B    0MS

 //

 #include <cstdio>

 #include <queue>

 using namespace std;

 int main()

 {

     const int MAXN = ;

     queue<int> qq;

     int i;

     int n;

     int x, y;

     int r;

     int a[MAXN][];

     int c[MAXN];

     bool first_node;

     char s[];

     while(scanf("%d", &n) == ){

         for(i = ; i < n; ++i){

             scanf("%d", &a[i][]);

             c[i] = ;

         }

         for(i = ; i < n; ++i){

             scanf("%s", s);

             if(s[] == 'd'){

                 scanf("%d%d", &x, &y);

                 a[i][] = x - ;

                 a[i][] = y - ;

                 ++c[x - ];

                 ++c[y - ];

             }else if(s[] == 'l'){

                 scanf("%d", &x);

                 a[i][] = x - ;

                 a[i][] = -;

                 ++c[x - ];

             }else if(s[] == 'r'){

                 scanf("%d", &y);

                 a[i][] = -;

                 a[i][] = y - ;

                 ++c[y - ];

             }else{

                 a[i][] = a[i][] = -;

             }

         }

         r = -;

         for(i = ; i < n; ++i){

             if(c[i] == ){

                 r = i;

                 break;

             }

         }

         if(r < ){

             // invalid tree structure

             continue;

         }

         first_node = true;

         qq.push(r);

         while(!qq.empty()){

             x = qq.front();

             qq.pop();

             if(first_node){

                 printf("%d", a[x][]);

                 first_node = false;

             }else{

                 printf(" %d", a[x][]);

             }

             if(a[x][] != -){

                 qq.push(a[x][]);

             }

             if(a[x][] != -){

                 qq.push(a[x][]);

             }

         }

         printf("\n");

         while(!qq.empty()){

             qq.pop();

         }

     }

     return ;

 }

巴特西

剑指Offer - 九度1523 - 从上往下打印二叉树

最新文章

热门文章