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

using namespace std;

// 二叉树结点定义
struct TreeNode 
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//


// 使用一个状态栈的方法来模拟后序遍历
void postorderTraversal(TreeNode* root, TreeNode* n) {
    stack<TreeNode*> st1;
    stack<int> st2;
    TreeNode* cur = root;
    while(cur != NULL || !st1.empty())
    {
        while(cur != NULL)
        {
            st1.push(cur);
            st2.push(0);
            cur = cur->left;
        }
        TreeNode* p = st1.top();
        if(st2.top() == 0)
        {
            st2.top() = 1;
            cur = p->right;
        }else
        {
            if (p->val == n->val) {
                while (!st1.empty())
                {
                    cout << st1.top()->val << ' ';
                    st1.pop();
                    st2.pop();
                }
                return ;
            }
            st1.pop();
            st2.pop();
        }
    }
}




// 非递归后序遍历查找路径m->n
void postorder(TreeNode* root, TreeNode* n) 
{
    stack<TreeNode*> stk;
    TreeNode* cur = root;
    TreeNode* prev = NULL;

    while(cur || !stk.empty())
    {
        // 将当前节点及其左节点全部入栈
        while(cur)
        {
            stk.push(cur);
            cur = cur->left;
        }

        cur = stk.top();
        // 如果栈顶没有右子节点或右子节点已经访问完
        if(!cur->right || cur->right == prev)
        {
            if (cur->val == n->val) // 访问到目标结点n时
            {
                while(!stk.empty()) // 输出栈中元素
                {
                    cout << stk.top()->val << ' ';
                    stk.pop();
                }
                return ;
            }
            stk.pop();
            prev = cur;
            cur = nullptr;
        }
        else // 有右子节点且还未访问
            cur = cur->right;
    }
}


bool dfs(TreeNode* root, TreeNode* n)
{
    if (!root) return false;

    if (root == n || dfs(root->left, n) || dfs(root->right, n))
    {
        cout << root->val << ' ';
        return true;
    }
    return false;
}



void postorderTraversal2(TreeNode* root, TreeNode* n) {
    stack<TreeNode*> stk1;
    stack<int> stk2; // 判断当前处于stk1栈顶的元素是否可以访问，0代表不能访问
    TreeNode* p = root;
    vector<int> ans;
    while (!stk1.empty() || p) 
    {
        while (p) {
            stk1.push(p);
            stk2.push(0);
            p = p->left;
        }
        TreeNode* u = stk1.top();
        if (stk2.top() == 0) {
            stk2.top() = 1;
            p = u->right;
        } else {
            if (u->val == n->val) // 访问到目标结点n时
            {
                while(!stk1.empty()) // 输出栈中元素
                {
                    cout << stk1.top()->val << ' ';

                    stk1.pop();
                }
                return ;
            }
            stk2.pop();
            stk1.pop();
            ans.push_back(u->val);
        }

    }

   // return ans;
}


int main() 
{
    // 构建一个二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    TreeNode* m = root;         // 选择m和n
    TreeNode* n = root->right->left;

    // 采用非递归后序遍历，最后访问根结点，访问到目标结点n时，
    // 栈中所有元素均为该结点的祖先，依次出栈打印即可。
    postorder(m, n);            // 调用后序遍历查找路径m->n
    cout << endl;
    postorderTraversal(m, n);
    cout << endl;
    dfs(m, n);
    cout << endl;
    postorderTraversal2(m, n);
    return 0;
}