有关树的遍历的非递归网上有很多了，这里把三种写法总结成类似的模板形式，方便记忆。

先序遍历

使用stack辅助运算先序遍历的顺序是“根-左-右”，算法为：

1. 将根节点push到栈中
2. 循环检测栈是否为空，若不空，则取出栈顶元素，保存其值，然后看其右子节点是否存在，若存在，则push到栈中。再看其左子节点，若存在，则push到栈中。

class solution{
    public:
        vector<int> preorderTraversal(TreeNode* root){
            vector<int>res;
            stack<TreeNode*>s;
            TreeNode *p = root;
            while(!s.empty() || p){
                if(p){ //若p节点存在
                    s.push(p); //将p加入栈中
                    res.push_back(p->val); //将p的节点值保存到res中
                    p = p->left; //指向下一个左子节点
                }
                else{// 若p节点不存在
                    TreeNode* t = s.top(); //取出栈顶节点
                    s.pop();
                    p = t->right; //将p指向栈顶节点的右子节点
                }
            }
            return res;
        }
};

中序遍历

从根节点开始，先将根节点压入栈，然后再将其所有左子结点压入栈，然后取出栈顶结点，保存结点值，再将其指针移到右子节点上，若存在右子结点，则在下次循环中又可以将其所有左子结点压入栈中，这样就保证了访问顺序为左-根-右。

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

后序遍历

先将先序遍历的根-左-右变成根-右-左，再翻转变为左-右-根，翻转方式为改变结构res的加入顺序，然后把更新辅助结点p的左右顺序换一下。

vector<int> PostorderTraversal(TreeNode* root){
    vector<int>res;
    stack<TreeNode*>s;
    TreeNode *p = root;
    while(!s.empty() || p){
        if(p){
            s.push(p);
            res.insert(res.begin(),p->val);
            p = p->right;
        }
        else{
            TreeNode *t = s.top()
            s.pop();
            p = t->left;
        }
        return res;
    }
}