1、简介我们在递归的时候说到过，一般我们如果想把递归的算法转换至非递归的实现，我们可以自己利用辅助栈来代替系统栈保存一些信息。所以在实现二叉树的三种非递归遍历的时候，我们需要开辟一个辅助栈来保存一些信息。2、二叉树结点结构/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) :   val(x), left(NULL), right(NULL) { }};*/3、先序遍历2.1 实现思路我们只需要开辟一个栈，先让根节点入栈。只要栈不空，我们循环的访问栈内每一位结点，如果访问的当前结点有孩子，让结点的右孩子左孩子依次入栈即可。（因为栈是先进后出，先序遍历是根左右，所以我们入栈的时候是先让右孩子入栈）。3.2 代码实现class Solution {public:    void preorderTraversal(TreeNode* root) {        stack<TreeNode*> s;        s.push(root);        while(!s.empty()){            TreeNode *temp = s.top();            s.pop();            if(!temp) continue;            cout<<temp->val<<" ";            if(temp->right) s.push(temp->right);            if(temp->left) s.push(temp->left);        }    }};4、中序遍历4.1 实现思路中序遍历的顺序是左根右，所以我们要先要访问到最左的那个结点（while(t){t= t->left}）。在访问最左结点的过程中将路径上的结点入栈。然后当栈不为空的时候循环访问即可。比如说最左的结点是1号结点，其父节点是2号结点。那么在找1号结点的过程中2号结点必定已入栈并且在1号结点下面。所以访问完1号结点后，接着会访问2号结点，只需在访问完2号结点时，将当前指针指向其右子树就会去访问其右子树。总体下来的顺序就是左根右。4.2 代码实现class Solution {public:    void inorderTraversal(TreeNode* root) {        stack<TreeNode*> s;        TreeNode *t = root;        while(!s.empty() || t){            while(t){ //找到最左的那个结点                s.push(t);                t = t -> left;            }            if(!s.empty()){                TreeNode *temp = s.top();                s.pop();                cout<<temp->val<<" ";                t = temp->right;            }        }    }};5、后序遍历5.1 实现思路后序遍历的非递归实现相较于先序和中序有点复杂。因为我们需要记录下结点的状态，后序遍历的顺序是左右根，我们在访问完左孩子去访问右孩子的时候，要经过根节点，所以我们要记录一下根结点的状态，如果这个根节点访问过了才输出。5.2 代码实现由于要记录每个结点的状态，我们有两种可以实现的方式：第一种是在二叉树结点的结构体内加一个标志位；第二种是我们采用对组的形式，每个结点绑定一个bool值。在这里我们使用对组的方式实现。class Solution {public:    void postorderTraversal(TreeNode* root) {        stack<pair<TreeNode*, bool> > s;        s.push(make_pair(root, false)); //根节点入栈        bool visited;        while(!s.empty()){            pair<TreeNode*, bool> p = s.top();            s.pop();            visited = p.second;            if(!p.first){                 continue;            }            if(visited){ //如果该节点被访问过才输出                cout<<p.first->val<<" ";            }           else            {                 s.push(make_pair(p.first, true));                if(p.first->right) s.push(make_pair(p.first->right, false));                if(p.first->left) s.push(make_pair(p.first->left, false));            }        }    }};