二叉树前序、中序、后序遍历的迭代实现

二叉树的前序、中序、后序遍历用递归实现较为简单。然而，利用递归实现则有一些挑战。现将几种常见的实现方式做简单介绍：

二叉树节点定义如下：

struct ListNode {
     int val;
      ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
};

一、前序遍历

前序遍历的顺序为：中，左，右。至少有两种方案：

//方案一：先后将右子树和左子放入栈中，利用栈后入先出的原理遍历。
 vector<int> preorderTraversal(TreeNode *root) {
     vector<int> res;
     if(!root)
         return res;
     stack<TreeNode*> st;
     st.push(root);
     while(!st.empty()){
         TreeNode* p = st.top();
         res.push_back(p->val);
         st.pop();
         if(p->right) st.push(p->right);
         if(p->left) st.push(p->left);
     }
     return res;
 }

//方案二：循环左子数，将右子树放入栈中。左子树为空时，依次弹栈，从最下层开始访问右子树。
 vector<int> preorderTraversal(TreeNode *root) {
     vector<int> res;
     if(!root)
         return res;
     stack<TreeNode*> st;
     st.push(root);
     while(!st.empty()){
         TreeNode* p = st.top();
         res.push_back(p->val);
         st.pop();
         while(p->left){
             res.push_back(p->left->val);
             if(p->right) st.push(p->right);
             p = p->left;
         }
         if(p->right) st.push(p->right);
     }
     return res;
 }

二、中序遍历

中序遍历的顺序为：左，中，右。其经典思路为：当前节点有左子节点时，将当前节点压栈，并将左子节点作为当前处理；当前节点无左子节点时，表示左子树都已遍历完成，此时访问当前节点，并将右子节点设为当前节点。

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

三、后续遍历

后序遍历的顺序为：左，右，中。以下给出两种方案：

//方案一：当前节点被读取的条件为：无左右孩子，或者上一次读取的为其左右孩子。
//否则按照先右后左的方式对子节点压栈。

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

//方案二：后序遍历有一种巧妙的方式：前序遍历根节点，先后将左右子节点压栈。
//这样的遍历顺序为：中，右，左。最后reverse结果，则遍历结果变为：左，右，中。

 vector<int> postorderTraversal(TreeNode *root){
     vector<int> res;
     if(!root)  
         return res;
     stack<TreeNode *> st;
     st.push(root);
     while(!st.empty()){
         TreeNode * p = st.top();
         res.push_back(p->val);
         st.pop();
         if(p->left) st.push(p->left);
         if(p->right) st.push(p->right);
     }
     reverse(res.begin(), res.end());
     return res;        
 }