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));
            }
        }
    }
};