题解 | 二叉树遍历（这才是清华要的基础解法）

直接建树当然能做，但是代码量太大；

然而，作为清华的题，理想的解法是，用栈显示实现树的遍历；

原理如下：

元素按先序入栈，第一次遇到时先不管，遇到空节点退回时，第二次遇到这个节点再输出，即可转化为中序遍历；

可以发现，整个过程与递归函数如出一辙²；

观察输入数据，也可以注意到，按照#出现的顺序，找左侧未输出过的最近元素输出，就是正确答案；

备注：

1. 题目中说有多组数据，而实际上的测试用例只有一组，有的同学可未必写对了；
2. 函数调用本身就是通过栈实现的，递归的函数，是可以显示的写出的；

#include <iostream>
using namespace std;

int main() {
    char stk[100], c;
    int top=-1;
    while (cin>>c && c != EOF) {
        if(c == '\n') {
            cout<<endl;
            top=-1;
        }
        else if(c == '#'){
            if(top == -1) continue;
            cout<<stk[top--]<<' ';
        } 
        else stk[++top] = c;
    }
}