二叉树的前中后序遍历（非递归）

class TreeNode
{
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode():val(NULL),left(nullptr),right(nullptr){}
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        if(root == nullptr) return res;
        TreeNode *cur = root;
        sta.push(root);
        while(!sta.empty())
        {
            cur = sta.top();
            sta.pop();
            res.push_back(cur->val);
            //先压入右 左 ，出栈才能为左 右
            if(cur->right) sta.push(cur->right);
            if(cur->left) sta.push(cur->left);
        }
        return res;
    }
    vector<int> inorderTraversal(TreeNode* root)
    {
        if(root == nullptr) return res;
        TreeNode *cur = root;
        while(cur != nullptr || !sta.empty())
        {
            if(cur != nullptr)
            {
                sta.push(cur);
                cur = cur->left;
            }
            else{
                cur = sta.top();
                sta.pop();
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
        return res;
    }
    vector<int> postorderTraversal(TreeNode* root)
    {
        if(root == nullptr) return res;
        TreeNode *cur = root;
        sta.push(root);
        while(!sta.empty())
        {
            cur = sta.top();
            sta.pop();
            res.push_back(cur->val);
            if(cur->left) sta.push(cur->left);
            if(cur->right) sta.push(cur->right);
        }
        reverse(res.begin(),res.end());
        return res;
    }

private:
    stack<TreeNode*> sta;
    vector<int> res;
};