#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 preorder(treenode *root)
{
    if(!root) return;
    cout<<root->val<<' ';
    preorder(root->left);
    preorder(root->right);
}
//非递归
void preorder2(treenode *root)
{
    stack<treenode*> s;
    s.push(root);

    while(!s.empty())
    {
        treenode *t=s.top();
        s.pop();

        cout<<t->val<<' ';
        if(t->right)s.push(t->right);
        if(t->left) s.push(t->left);
    }
}

//中序遍历
//递归
void inorder(treenode *root)
{
    if(!root) return;
    inorder(root->left);
    cout<<root->val<<" ";
    inorder(root->right);
}
//非递归
void inorder2(treenode *root)
{
    stack<treenode*> s;
    treenode *cur=root;

    while(cur||!s.empty())
    {
        while(cur)
        {
            s.push(cur);
            cur=cur->left;
        }

        cur=s.top();
        s.pop();

        cout<<cur->val<<" ";
        cur=cur->right;
    }
}

//后序遍历
//递归
void postorder(treenode *root)
{
    if(!root) return ;
    postorder(root->left);
    postorder(root->right);
    cout<<root->val<<" ";
}
//非递归
void postorder2(treenode *root)
{
    stack<treenode*> s;
    treenode* cur=root;
    treenode* preve=NULL;

    while(cur||!s.empty())
    {
        while(cur)
        {
            s.push(cur);
            s.push(cur->left);
        }

        cur=s.top();
        if(!cur->right||cur->right==preve)
        {
            s.pop();
            cout<<cur->val<<' ';

            preve=cur;
            cur=nullptr;
        }
        else
        {
            cur=cur->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();
        }
}
treenode* lowestCommonAncester(treenode* root,treenode *q,treenode*p)
{
    if(!root) return NULL;
    if(root==q||root==p) return root;

    treenode* left=lowestCommonAncester(root->left,q,p);
    treenode* right=lowestCommonAncester(root->right,q,p);

    if(left&&right) return root;
    if(left==NULL) return right;
    else return left;
}

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;

    /*cout<<"先序遍历："<<endl;
    preorder(root);
    cout<<endl;
    preorder2(root);
    cout<<endl;

    cout<<"中序遍历："<<endl;
    inorder(root);
    cout<<endl;
    inorder2(root);
    cout<<endl;*/

    /*cout<<"后序遍历："<<endl;
    postorder(root);
    cout<<endl;
    postorder2(root);
    cout<<endl;*/

    /*cout<<"层序遍历："<<endl;
    levelorder(root);
    cout<<endl;
    levelorder2(root);
    cout<<endl;*/
    //levelorder4(root);

    return 0;
}