#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <stack>

using namespace std;
struct TreeNode
{
	int val;
	TreeNode* left = nullptr;
	TreeNode* right = nullptr;

	TreeNode(int v)
		:val(v)
	{}
};
//非递归遍历二叉树

//前序遍历
vector<int> preorderTraversal(TreeNode* root) 
{
    //非递归，借助栈来实现
    //分为两大的问题，一，左路结点， 二，左路节点的右子树
    stack<TreeNode*> st;
    vector<int> arr;

    TreeNode* cur = root;
    while (cur || !st.empty())
    {
        //1.先访问左路结点
        while (cur)
        {
            st.push(cur);
            arr.push_back(cur->val);
            cur = cur->left;//向左走，先把左路结点全部放到栈
        }

        //2.开始处理最左结点的右子树问题
        TreeNode* top = st.top();
        st.pop();
        //访问每个左路结点的右子树就是上述过程的子问题，把左节点的第一个右结点
        //看成一个树的根节点。
        cur = top->right;
    }
    return arr;
}

//中序遍历
vector<int> inorderTraversal(TreeNode* root) {
    //思路跟前序的非递归相似
    stack<TreeNode*> st;
    vector<int> arr;

    TreeNode* cur = root;
    while (cur || !st.empty())
    {
        while (cur)
        {
            st.push(cur);
            cur = cur->left;
        }

        TreeNode* top = st.top();
        st.pop();

        arr.push_back(top->val);

        cur = top->right;//一个结点从栈中出来就意味着，它和它的左子树访问完了
    }

    return arr;
}

//后序遍历
vector<int> postorderTraversal(TreeNode* root) {
    //思路跟前序的非递归相似
    stack<TreeNode*> st;
    vector<int> arr;
    TreeNode* cur = root;
    TreeNode* prev = nullptr;

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

        TreeNode* top = st.top();

        if (top->right == nullptr || top->right == prev)
        {
            //满足第一个条件的时候，处理的就是左结点
            //满足第二个条件的时候，处理的就是根结点,,在满足第二个条件的时候，就说明左右子树都处理完了
            arr.push_back(top->val);
            prev = top;
            st.pop();
        }
        else
            cur = top->right;//开始遍历右子树
    }
    return arr;
}


void test1(TreeNode* root)
{
    vector<int> v;
    v = preorderTraversal(root);

    for (auto& e : v)
    {
        cout << e << " ";
    }
    cout << endl;
}

void test2(TreeNode* root)
{
    vector<int> v;
    v = inorderTraversal(root);

    for (auto& e : v)
    {
        cout << e << " ";
    }
    cout << endl;
}

void test3(TreeNode* root)
{
    vector<int> v;
    v = postorderTraversal(root);

    for (auto& e : v)
    {
        cout << e << " ";
    }
    cout << endl;
}

int main()
{
    TreeNode* n0 = new TreeNode(0);
    TreeNode* n1 = new TreeNode(1);
    TreeNode* n2 = new TreeNode(2);
    TreeNode* n3 = new TreeNode(3);
    TreeNode* n4 = new TreeNode(4);
    TreeNode* n5 = new TreeNode(5);
    n3->left = n1;
    n1->left = n0;
    n1->right = n2;
    n3->right = n4;
    n4->right = n5;

    //test1(n3);//前序
    //test2(n3);//中序
    test3(n3);//后序

	return 0;
}