问题说明

Gold King已经掌握了二叉树的先中后序递归形式遍历，由于是两个递归调用，让程序执行的效率低下，于是Gold King想着有没有优化的方式。 在对Gold King的二叉树遍历1中的二叉搜索树观察研究中，Gold King发现一种先序的非递归实现方式： 1、将二叉树的根节点当作当前正在遍历的结点 2、若当前结点非空，则先访问该结点，并将该结点压进栈，再将其左孩子结点作为当前遍历节点，重复步骤2，直到遍历到的结点为空为止 3、之后若栈非空，则栈顶结点出栈，并将当前结点的右孩子结点作为当前遍历结点 重复步骤2和3，直到栈为空且当前结点为空为止。 请你实现非递归实现的二叉树先序遍历。

输入格式

第一行输入一个整数n，表示有n个数。 第二行输入n个整数ai，表示对应n个数据（题目保证ai各不相同）。## 输出格式

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

输入数据 1

7
23 13 10 30 54 46 77

输出数据 1

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

提示

3<=n<=100 1<=ai<=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。

</span> ## 来源/分类

算法培训-21-二叉树