二叉树非递归遍历

#include <stdio.h>
#include <vector>
#include <stack>
#include <string>
struct node
{
    int val;
    node *left, *right;
    node(int val) : val(val), left(nullptr), right(nullptr) {}
};
//先序遍历,中左右
std::vector<int> pre_order_traverse(node *root)
{

    std::vector<int> ans;
    std::stack<node *> s;
    node *p = root;
    while (p || !s.empty())
    {
        if (!p)
        {
            p = s.top();
            s.pop();
        }
        else
        {
            ans.push_back(p->val);
            if (p->right)
                s.push(p->right);
            p = p->left;
        }
    }
    return ans;
}

//中序遍历,左中右
std::vector<int> in_order_traverse(node *root)
{

    std::vector<int> ans;
    std::stack<node *> s;
    node *p = root;
    while (p || !s.empty())
    {
        if (!p)
        {
            p = s.top();
            ans.push_back(p->val);
            p = p->right;
            s.pop();
        }
        else
        {
            s.push(p);
            p = p->left;
        }
    }
    return ans;
}

//后序遍历,左右中
std::vector<int> post_order_traverse(node *root)
{
    //先中右左然后反序

    std::vector<int> reversed_ans;
    std::stack<node *> s;
    node *p = root;
    while (p || !s.empty())
    {
        if (!p)
        {
            p = s.top();
            s.pop();
        }
        else
        {
            reversed_ans.push_back(p->val);
            if (p->left)
                s.push(p->left);
            p = p->right;
        }
    }

    return std::vector<int>(reversed_ans.rbegin(), reversed_ans.rend());
}
struct foo
{
    int val;
    foo(int val) : val(val) {}
};
foo f() { return foo(50); }
int main()
{

    node *root = new node(1);
    root->left = new node(3);
    root->right = new node(2);
    root->left->left = new node(4);
    root->left->right = new node(5);
    std::vector<int> ans = post_order_traverse(root);
    for (int temp : ans)
        printf("%d ", temp);

    return 0;
}