递归+迭代（借用栈）

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */
//递归版本大家基本都会
//但是我觉得迭代版本的写法就很灵活，特别是中序和后序遍历
//巧妙借用stack容器的特性，大家可以多关注下迭代版本

class Solution {
private:
    vector<int> preOrder,inOrder,postOrder;
public:
    vector<vector<int> > threeOrders(TreeNode* root) {
        vector<vector<int>> ans;
        if(!root) return ans;

        PreOrderIteratively(root);
        InOrderIteratively(root);
        PostOrderIteratively(root);

        ans.push_back(preOrder);
        ans.push_back(inOrder);
        ans.push_back(postOrder);

        return ans;
    }
   void PreOrder(TreeNode* root){
        if(!root) return ;
        preOrder.push_back(root->val);
        PreOrder(root->left);
        PreOrder(root->right);

    }
    void InOrder(TreeNode* root){
        if(!root) return;

        InOrder(root->left);
        inOrder.push_back(root->val);
        InOrder(root->right);

    }
    void PostOrder(TreeNode* root){

        if(!root) return ;

        PostOrder(root->left);
        PostOrder(root->right);
        postOrder.push_back(root->val);

    }

    void PreOrderIteratively(TreeNode* root){
        if(root==nullptr)
            return;

        stack<TreeNode*> stk;
        stk.push(root);
        TreeNode* p=nullptr;
        while(!stk.empty()){
            p=stk.top();
            stk.pop();
            preOrder.push_back(p->val);
            if(p->right)
                stk.push(p->right);
            if(p->left)
                stk.push(p->left);
        }
    }
    void InOrderIteratively(TreeNode* root){
        if(!root)
            return;

        stack<TreeNode*> stk;
        TreeNode* p=root;
        while(p || !stk.empty()){
            if(p){
                stk.push(p);
                p=p->left;
            }
            else{
                p=stk.top();
                stk.pop();
                inOrder.push_back(p->val);
                p=p->right;
            }

        }



    }
    void PostOrderIteratively(TreeNode* root){
        if(!root)
            return;

        stack<TreeNode*> stk;
        stk.push(root);
        TreeNode* p=nullptr;
        while(!stk.empty()){
            p=stk.top();
            stk.pop();
            postOrder.insert(postOrder.begin(), p->val);

            if(p->left)
                stk.push(p->left);

            if(p->right)
                stk.push(p->right);
        }
    }


};