递归的本质是将调用函数压入栈中，既然递归可以实现二叉树的遍历，那么迭代也可以实现二叉树的遍历。

一、使用迭代实现二叉树遍历的难点

• 我们在访问二叉树的时候，一定是先访问根节点，然后访问两个孩子节点；并且只能通过根访问孩子；不能通过孩子访问根。
• 而三种不同的方法遍历二叉树的差异实际上是什么时候对根结点进行处理（将根节点压入结果中）
• 在二叉树中，每一个节点都可以视作其他节点的根节点，最后一行可以视作两个孩子均为空
• 在递归方法中，我们通过控制递归调用和对节点处理的顺序，可以控制根结点处理的时机。但在循环遍历中，我们将二叉树的节点压入栈中，我们必须通过控制节点在栈中的顺序来控制何时对节点进行处理。

因此，我们在将一个节点及其左右孩子节点压入栈中时，必须根据遍历要求调整压入顺序；同时，由于一个节点通常会同时具有根节点和孩子节点的身份，因此一个节点会被调整两次，所以我们必须对已经调整好顺序的节点作标记，以便再次在栈中访问到他的时候将他输出到结果中。

算法的时间复杂度：O(n）
算法的空间复杂度：O(h)，h为树的高度，深度遍历每一层会压入一个栈；其与n的联系为：

• 平均空间复杂度为O(logn),发生在树比较平衡时
• 最坏空间复杂度为O(n)，发生在树严重向左偏的时候(左节点多余右节点)
• 最好空间复杂度为O(1)，发生在树严重向右偏的时候

二、递归法遍历的代码实现

1、中序遍历

我们通过在调整好顺序的元素后面压入一个nullptr来标记他们；当访问栈顶元素为nullptr时，我们就将nullptr前面的元素弹出到结果中

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
    	//初始化栈和结果
        vector<int> result;
        stack<TreeNode*> st;
        
        //处理空树情况并将第一个根节点压入栈
        if (root != NULL) st.push(root);
        
        //只有栈空了，遍历才结束
        while (!st.empty()) {
	
			//获取当前栈顶，将其作为根节点
            TreeNode* node = st.top();

			//如果栈顶不是空，说明该节点仍需调整
            if (node != NULL) {
            
				//将根节点弹出，并按照遍历要求重新将根节点和其左右孩子节点压入栈中
				//根节点此次调整后不会再调整，因此在根节点后面标记nullptr
				//而左右孩子节点将作为其他节点的根节点，后续还需调整顺序，因此不能标记
                st.pop(); 
                if (node->right) st.push(node->right);  //添加右节点
                st.push(node);                          //添加根节点
                st.push(NULL);  						//标记根节点
                if (node->left) st.push(node->left);    // 添加左节点
            } else { 
            
            	//如果栈顶为nullptr，说明该节点已经排好顺序，可以输出到结果
            	// 将空节点弹出并重新取出栈中元素，将其弹出到结果
                st.pop();           
                node = st.top();   
                st.pop();
                result.push_back(node->val); 
            }
        }

		//返回结果
        return result;
    }
};

这里需要注意的是，根节点与左右孩子节点压入栈的顺序和遍历要求顺序是相反的。因为出栈弹出到结果的时候会将栈中的元素顺序反转过来。

2、前序遍历和后续遍历

在这样的框架下，前序遍历和后续遍历只需要改动根节点和左右孩子节点压入栈的顺序即可。

前序遍历

            if (node != NULL) {
            
				//将根节点弹出，并按照遍历要求重新将根节点和其左右孩子节点压入栈中
				//根节点此次调整后不会再调整，因此在根节点后面标记nullptr
				//而左右孩子节点将作为其他节点的根节点，后续还需调整顺序，因此不能标记
                st.pop(); 
                if (node->right) st.push(node->right);  //添加右节点
                if (node->left) st.push(node->left);    // 添加左节点
                st.push(node);                          //添加根节点
                st.push(NULL);  						//标记根节点

后续遍历

            if (node != NULL) {
            
				//将根节点弹出，并按照遍历要求重新将根节点和其左右孩子节点压入栈中
				//根节点此次调整后不会再调整，因此在根节点后面标记nullptr
				//而左右孩子节点将作为其他节点的根节点，后续还需调整顺序，因此不能标记

				//前序遍历中下面这两句话可以省略，直接对栈顶元素进行标记就可以，这是因此此时访问顺序和处理顺序是一致的
                st.pop(); 
                st.push(node);                          //添加根节点
                
                st.push(NULL);  						//标记根节点                
                if (node->right) st.push(node->right);  //添加右节点
                if (node->left) st.push(node->left);    // 添加左节点

本文参考资料：代码随想录 https://github.com/youngyangyang04/leetcode-master