A354 | $Gold King的二叉树遍历3$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

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

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

第一行输出对应二叉搜索树的先序遍历结果， 第二行输出每次当前遍历输出时，栈中元素个数。 每个数据占 $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

C++ 编辑器

输入

输出