A265.Gold King的二叉树遍历3

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

Gold King已经掌握了二叉树的先中后序递归形式遍历,由于是两个递归调用,让程序执行的效率低下,于是Gold King想着有没有优化的方式。

在对Gold King的二叉树遍历11中的二叉搜索树观察研究中,Gold King发现一种先序的非递归实现方式:

1、将二叉树的根节点当作当前正在遍历的结点

2、若当前结点非空,则先访问该结点,并将该结点压进栈,再将其左孩子结点作为当前遍历节点,重复步骤22,直到遍历到的结点为空为止

3、之后若栈非空,则栈顶结点出栈,并将当前结点的右孩子结点作为当前遍历结点
重复步骤2233,直到栈为空且当前结点为空为止。

请你实现非递归实现的二叉树先序遍历。

输入格式

第一行输入一个整数nn,表示有nn个数。
第二行输入nn个整数aia_i
,表示对应nn个数据(题目保证aia_i
各不相同)。

输出格式

第一行输出对应二叉搜索树的先序遍历结果,
第二行输出每次当前遍历输出时,栈中元素个数。
每个数据占55个域宽。

输入输出样例

  • 输入#1

    7
    23 13 10 30 54 46 77

    输出#1

     23   13   10   30   54   46   77
        1    2    3    1    1    2    1

说明/提示

3n1001ai10003\le n\le 100 1 \le a i \le 1000
样例1数据构建的二叉树如下图:

对应先序遍历输出23时,栈中压入23,栈中个数为1;输出13时,栈中压入13,栈中个数为2;输出10时,栈中压入10,栈中个数为3;输出30时,栈中已经弹出10、13、23,再压入30,栈中个数为1;输出54时,栈中已经弹出30,再压入54,栈中个数为1;输出46时,栈中压入46,栈中个数为2;输出77时,栈中已经弹出46、54,再压入23,栈中个数为1。

首页