#include <iostream>
#include <queue>
#include <stack>
using namespace std;

struct treenode
{
    char val;
    treenode* left;
    treenode* right;
    treenode():val(0),left(NULL),right(NULL){}
    treenode(char x):val(x),left(NULL),right(NULL){}
    treenode(char x,treenode *left,treenode *right):val(x),left(left),right(right){}
};

//层次遍历
void levelorder(treenode *root)
{
    queue<treenode*> q;
    q.push(root);

    while(!q.empty())
    {
        treenode *t=q.front();
        q.pop();
        cout<<t->val<<' ';

        if(t->left)q.push(t->left);
        if(t->right)q.push(t->right);
    }
}

//层次遍历逆转，从下到上，从右到左
void levelorder2(treenode *root)
{
    queue<treenode*> q;
    stack<treenode*> s;
    q.push(root);

    while(!q.empty())
    {
        treenode *t=q.front();
        q.pop();

        s.push(t);
        if(t->left)q.push(t->left);
        if(t->right)q.push(t->right);
    }

    while(s.size())
    {
        cout<<s.top()->val<<" ";
        s.pop();
    }
}


//从上到下，从右到左
void levelorder3(treenode *root)
{
    queue<treenode*> q;
    stack<treenode*> s;
    q.push(root);

    while(q.size())
    {
        int n=q.size();
        while(n--)
        {
            treenode *o=q.front();
            q.pop();
            s.push(o);

            if(o->left) q.push(o->left);
            if(o->right) q.push(o->right);
        }
        while(s.size())
        {
        treenode *t=s.top();
        s.pop();
        cout<<t->val<<" ";
        }
    }

}
//从下到上，从左到右
void levelorder4(treenode *root)
{
    queue<treenode*> q;
    stack<treenode*> s1;//入栈
    stack<treenode*> s2;//结果栈
    q.push(root);

    while(!q.empty())
    {
        int n=q.size();
        while(n--)
        {
            treenode* t=q.front();
            q.pop();

            s1.push(t);
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
        while(s1.size())
        {
            s2.push(s1.top());
            s1.pop();
        }
    }
    while(s2.size())
        {
            cout<<s2.top()->val<<' ';
            s2.pop();
        }
}

int main()
{
    treenode *root=new treenode('A',new treenode('B',
    new treenode('D'),new treenode('E')),new treenode('C'));


    cout<<"     A  "<<endl;
    cout<<" B       C  "<<endl;
    cout<<"D E    "<<endl;

    levelorder4(root);
    return 0;
}